作者：困了电视剧

专栏：《数据结构--Java》

文章分布：这是关于数据结构链表的文章，包含了自己的无头单向非循环链表和无头双向链表实现简单实现，和相关题目，想对你有所帮助。

 

 

目录

无头单向非循环链表实现

无头双向链表实现

链表的相关题目

移除链表元素

反转一个单链表

链表的中间结点

链表中倒数第k个结点

---

无头单向非循环链表实现

public class SingleLinkedList {static class Node {public int val;//存储的数据public Node next;//存储下一个节点的地址//public Node(){}public Node (int val) {this.val = val;}}public Node head;public int size=0;//头插法public void addFirst(int data){Node node = new Node(data);node.next=head;head = node;size++;}//尾插法public void addLast(int data){Node node = new Node(data);if ( head==null ){head=node;return;}Node tmp=head;while ( tmp.next!=null ){tmp=tmp.next;}tmp.next=node;size++;}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data){//先判断idx是否合法if ( index>size||index<0 ){return false;}if ( head==null ){return false;}Node node = new Node(data);Node cur=head;int cnt=0;while ( cnt!=index ){cur=cur.next;cnt ++;}node.next=cur.next;cur.next=node;return true;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){if ( head==null ){return false;}Node cur = head;while ( cur!=null ){if ( cur.val==key ){return true;}cur=cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){if ( head==null ){return;}if ( head.val==key ){head=head.next;return;}Node cur = head;while ( cur.next!=null ){if ( cur.next.val==key ){cur.next=cur.next.next;return;}cur=cur.next;}}//删除所有值为key的节点public void removeAllKey(int key){if ( head==null ){return;}Node pre=head;Node cur=head.next;while ( cur!=null ){if ( cur.val==key ){cur=cur.next;pre.next=cur;}else{pre=cur;cur=cur.next;}}if ( head.val==key ){head=head.next;}return;}//得到单链表的长度public int size(){return this.size;}public void display(){if ( head==null ){return;}Node cur=head;while ( cur!=null ){System.out.println(cur.val+" ");}}public void clear(){head=null;}
}

无头双向链表实现

public class MyLinkedList {//内部类构造一个链表数据结构static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(){}public ListNode(int val){this.val=val;}}private ListNode first;private ListNode last;private int size=0;MyLinkedList(){}//头插法public void addFirst(int data){ListNode node=new ListNode(data);if ( first==null ){first=node;last=node;}else{node.next=first;first.prev=node;first=node;}size++;}//尾插法public void addLast(int data){ListNode node=new ListNode(data);if ( first==null ){first=node;last=node;}else{last.next=node;node.prev=last;last=node;}size++;}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data){//判断这个index是否合法if ( index<0 || index>size ){return false;}ListNode node=new ListNode(data);ListNode cur=first;for ( int i=0;i<index;i++ ){cur=cur.next;}if ( cur==first ){node.next=cur;cur.prev=node;first=node;}else if ( cur==last ){last.next=node;node.prev=last;last=node;}else{node.next=cur;node.prev=cur.prev;cur.prev.next=node;cur.prev=node;}return true;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur=first;while ( cur!=null ){if ( cur.val==key ){return true;}cur=cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur=first;while ( cur!=null ) {if (cur.val == key) {//判断是不是头或尾if (cur == first) {first=first.next;if ( first!=null ){first.prev=null;}} else if (cur == last) {last=last.prev;last.next=null;} else {cur.prev.next=cur.next;cur.next.prev=cur.prev;}return;}cur = cur.next;}}//删除所有值为key的节点public void removeAllKey(int key){ListNode cur=first;while ( cur!=null ) {if (cur.val == key) {//判断是不是头或尾if (cur == first) {first=first.next;if ( first!=null ){first.prev=null;}} else if (cur == last) {last=last.prev;last.next=null;} else {cur.prev.next=cur.next;cur.next.prev=cur.prev;}}cur = cur.next;}}//得到单链表的长度public int size(){return this.size;}//输出链表的内容public void display(){ListNode cur=first;while ( cur != null ){System.out.println(cur.val);cur=cur.next;}}public void clear(){first=null;last=null;}
}

链表的相关题目

移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/description/

class Solution {public ListNode removeElements(ListNode head, int val) {if ( head==null ){return null;}ListNode pre=head;ListNode cur=head.next;while ( cur!=null ){if ( cur.val==val ){cur=cur.next;pre.next=cur;}else{pre=cur;cur=cur.next;}}if ( head.val==val ){head=head.next;}return head;}
}

反转一个单链表

https://leetcode.cn/problems/reverse-linked-list/description/

将每一个结点的指向翻转一下，不需要重新遍历什么的。

class Solution {public ListNode reverseList(ListNode head) {if ( head==null ){return null;}ListNode cur = head.next;ListNode pre = head;pre.next = null;while ( cur != null ){ListNode nextNode = cur.next;cur.next = pre;pre = cur;cur = nextNode;}return pre;}
}

链表的中间结点

https://leetcode.cn/problems/middle-of-the-linked-list/description/

用快慢指针可以在O(n)的时间复杂度完成。

class Solution {public ListNode middleNode(ListNode head) {if ( head == null ){return null;}ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;}return slow;}
}

链表中倒数第k个结点

https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

用快慢指针的方法，快指针先跑k个，然后慢指针和快指针再按相同的速度跑 

public class Solution {public ListNode FindKthToTail(ListNode head,int k) {if ( head == null ){return null;}ListNode fast = head;ListNode slow = head;while (k != 0){if (fast != null){fast = fast.next;k--;}else{return null;}}while ( fast != null ){slow = slow.next;fast = fast.next;}return slow;}
}