带头节点单链表
1.优势：
1）当链表为空时，指针指向头结点，不会发生null指针异常
2）方便特殊操作（删除第一个有效节点或者插入一个节点在表头）
3）单链表加上头结点之后，无论单链表是否为空，头指针始终指向头结点，因此空表和非空表的处理也统一了，方便了单链表的操作，也减少了程序的复杂性和出现bug的机会。
4）代码更加简单易懂
2.相关操作
1）建立单链表 即建立一个头结点
static class Entry<T> { T data; // 链表节点的数据域 Entry<T> next; // 下一个节点的引用 public Entry(T data, Entry<T> next) { this.data = data; this.next = next; } } /** * 头节点的类型 * * @param <T> */ private static class HeadEntry<T> extends Entry<T> { int cnt; // 用来记录节点的个数 public HeadEntry(int cnt, T data, Entry<T> next) { super(data, next); this.cnt = cnt; } }
2）头插：新建节点next域指向头结点的next域，再将头结点next指向新节点。
public void insertHead(T val) {
Entry<T> newNode = new Entry<>(val, null);
newNode.next = this.head.next;
this.head.next = newNode;
}
3）尾插：从头结点开始遍历，当next出现null时，已经到达尾部，将next指向新节点即可
public void insertTail(T val) { Entry<T> temp = this.head; Entry<T> newNode = new Entry<>(val, null); while (temp.next != null) { temp = temp.next; } temp.next = newNode; }
4）删除值为val的节点 ：设置一前一后指针进行遍历，当后指针发现值为val的节点时，前指针的next域指向后指针的next域即可
public void remove(T val) { Entry<T> frontTemp = this.head; Entry<T> temp = frontTemp.next; while (temp.data != val) { frontTemp = frontTemp.next; temp = temp.next; } frontTemp.next = temp.next; }
5）逆置单链表 :将第二个有效节点不断进行头插操作，就会产生逆置效果
将链表从第二个有效节点开始一分为二，不断头插进前一链表
public void reverse() { if (this.head.next == null) { return; } Entry<T> cur = this.head.next.next; this.head.next.next = null; Entry<T> post = null; while (cur != null) { post = cur.next; cur.next = head.next; head.next = cur; cur = post; } }
6）获取倒数第k个节点的值：设置两个相距K的指针，当前指针到达链表尾部时，前指针指向倒数第k个节点
public T getLastK(int k) { Entry<T> cur1 = this.head.next; Entry<T> cur2 = cur1.next; for (int i = 1; i < k; i++) { cur2 = cur2.next; if (cur2 == null) { return null; } } while (cur2 != null) { cur1 = cur1.next; cur2 = cur2.next; } return cur1.data; }
7）判断链表是否有环，如果有，返回入环节点的值；否则返回null：
设置快慢指针，快指针一次移动两次，慢指针一次移动一次，如果出现快指针指向的节点等于慢指针指向的节点 ，即证明节点有环。
入环节点的求法：
设相遇点为A点；当快指针经过 x+2y+z个节点时时 慢指针走了x+y个节点 可得2（x+y）=x+2y+z 化简可得x=z；所以
fast从第一个节点开始走，slow从快慢指针相交的地方开始走，它们相遇的时候，就是环的入口节点
public T isLinkCircle() { //利用快慢指针检测是否有环 Entry<T> slow = this.head.next; Entry<T> quick = this.head.next; while (quick != null && quick.next != null) { slow = slow.next; quick = quick.next.next; if (slow == quick) { break; } } if (quick == null) { return null; } else { // fast从第一个节点开始走，slow从快慢指针相交的地方开始走，它们相遇的时候，就是环的入口节点 quick = this.head.next; while (quick != slow) { quick = quick.next; slow = slow.next; } return slow.data; } }
8)合并两个有序单链表
public void merge(Link<T> link) { Entry<T> p = this.head; Entry<T> p1 = this.head.next; Entry<T> p2 = link.head.next; // 比较p1和p2节点的值，把值小的节点挂在p的后面 while (p1 != null && p2 != null) { if (p1.data.compareTo(p2.data) >= 0) { p.next = p2; p2 = p2.next; } else { p.next = p1; p1 = p1.next; } p = p.next; } if (p1 != null) { // 链表1还有剩余节点 p.next = p1; } if (p2 != null) { // 链表2还有剩余节点 p.next = p2; } }
总源代码
class Link<T extends Comparable<T>> { // 指向单链表的第一个节点 Entry<T> head; public Link() { this.head = new Entry<>(null, null); } /** * 单链表的头插法 * * @param val */ public void insertHead(T val) { Entry<T> newNode = new Entry<>(val, null); newNode.next = this.head.next; this.head.next = newNode; } /** * 单链表的尾插法 * * @param val */ public void insertTail(T val) { Entry<T> temp = this.head; Entry<T> newNode = new Entry<>(val, null); while (temp.next != null) { temp = temp.next; } temp.next = newNode; } /** * 单链表中删除值为val的节点 * * @param val */ public void remove(T val) { Entry<T> frontTemp = this.head; Entry<T> temp = frontTemp.next; while (temp.data != val) { frontTemp = frontTemp.next; temp = temp.next; } frontTemp.next = temp.next; } /** * 逆置单链表 */ public void reverse() { if (this.head.next == null) { return; } Entry<T> cur = this.head.next.next; this.head.next.next = null; Entry<T> post = null; while (cur != null) { post = cur.next; cur.next = head.next; head.next = cur; cur = post; } } /** * 获取倒数第K个单链表节点的值 * 1.遍历一次链表，统计链表节点的个数length * 2.length-k * 只遍历一次链表，找出数 * * @param k */ public T getLastK(int k) { Entry<T> cur1 = this.head.next; Entry<T> cur2 = cur1.next; for (int i = 1; i < k; i++) { cur2 = cur2.next; if (cur2 == null) { return null; } } while (cur2 != null) { cur1 = cur1.next; cur2 = cur2.next; } return cur1.data; } /** * 判断链表是否有环，如果有，返回入环节点的值；否则返回null * * @return */ public T isLinkCircle() { //利用快慢指针检测是否有环 Entry<T> slow = this.head.next; Entry<T> quick = this.head.next; while (quick != null && quick.next != null) { slow = slow.next; quick = quick.next.next; if (slow == quick) { break; } } if (quick == null) { return null; } else { // fast从第一个节点开始走，slow从快慢指针相交的地方开始走，它们相遇的时候，就是环的入口节点 quick = this.head.next; while (quick != slow) { quick = quick.next; slow = slow.next; } return slow.data; } } /** * 打印单链表的所有元素的值 */ public void show() { Entry<T> temp = this.head.next; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } /** * 单链表的节点类型 * * @param <T> */ static class Entry<T> { T data; // 链表节点的数据域 Entry<T> next; // 下一个节点的引用 public Entry(T data, Entry<T> next) { this.data = data; this.next = next; } } /** * 头节点的类型 * * @param <T> */ private static class HeadEntry<T> extends Entry<T> { int cnt; // 用来记录节点的个数 public HeadEntry(int cnt, T data, Entry<T> next) { super(data, next); this.cnt = cnt; } } /** * 合并两个有序的单链表 * * @param link */ public void merge(Link<T> link) { Entry<T> p = this.head; Entry<T> p1 = this.head.next; Entry<T> p2 = link.head.next; // 比较p1和p2节点的值，把值小的节点挂在p的后面 while (p1 != null && p2 != null) { if (p1.data.compareTo(p2.data) >= 0) { p.next = p2; p2 = p2.next; } else { p.next = p1; p1 = p1.next; } p = p.next; } if (p1 != null) { // 链表1还有剩余节点 p.next = p1; } if (p2 != null) { // 链表2还有剩余节点 p.next = p2; } } }