链表的题目多涉及指针操作，需要画图显示步骤，不然容易搞混。
常用的套路有：
双指针（前驱后继指针、快慢指针、奇偶指针）
虚拟头节点（好处：需要前驱节点时，总能找到前驱节点。比如在删除头节点时，我们可以找到头节点的前驱。）
设计链表 https://leetcode.cn/problems/design-linked-list/description/
从0开始设计一个链表，实现get、add、delete方法
链表首先要声明链表节点
1 2 3 4 5 6 7 8 9 class ListNode { int val; ListNode next; ListNode(){} ListNode(int val) { this .val = val; this .next = null ; } }
再设计链表类
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class MyLinkedList { int size; ListNode head; public MyLinkedList () { size = 0 ; head = new ListNode (-1 ); } public int get (int index) { } public void addAtIndex (int index, int val) { } public void deleteAtIndex (int index) { } }
我们首先实现get方法。
1 2 3 4 5 6 7 8 9 public int get (int index) { if (index<0 || index>=size) return -1 ; ListNode cur = head; for (int i=0 ; i<=index; ++i) cur = cur.next; return cur.val; }
再看delete方法，这里就能看到虚拟头节点的好处了。删除一个节点需要知道它的前驱节点，让它的前驱指向它的后继；如果要删除0号节点即头节点，没有虚拟头节需要额外判断；
1 2 3 4 5 6 7 8 9 10 11 12 13 public void deleteAtIndex (int index) { if (index < 0 || index >= size) return ; ListNode cur = head; for (int i=0 ; i<index; ++i) cur = cur.next; cur.next = cur.next.next; --size; }
最后看add方法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public void addAtIndex (int index, int val) { if (index > size) return ; if (index < 0 ) index = 0 ; ListNode cur = head; for (int i=0 ; i<index; ++i){ cur = cur.next; } ListNode tmp = new ListNode (val); tmp.next = cur.next; cur.next = tmp; ++size; }
双指针应用 移除特定链表元素 https://leetcode.cn/problems/remove-linked-list-elements/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public ListNode removeElements (ListNode head, int val) { ListNode dummyNode = new ListNode (-1 ); dummyNode.next = head; ListNode pre = dummyNode; ListNode cur = dummyNode.next; while (cur != null ){ if (cur.val == val){ pre.next = cur.next; cur = pre.next; continue ; } pre = cur; cur = cur.next; } return dummyNode.next; } }
移除链表中某个特定节点需要知道它的前驱和后继，所以设立前后指针；虚拟头节点方便删除。
删除链表的倒数第N个节点 https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public ListNode removeNthFromEnd (ListNode head, int n) { ListNode dummyNode = new ListNode (-1 ); dummyNode.next = head; ListNode first = dummyNode; ListNode second = dummyNode; for (int i=0 ; i<n; ++i){ second = second.next; } while (second != null && second.next !=null ) { second = second.next; first = first.next; } first.next = first.next.next; return dummyNode.next; } }
快慢指针应用，快指针先走N步，然后再走到底。
相交链表 https://leetcode.cn/problems/intersection-of-two-linked-lists/
1 2 3 4 5 6 7 8 9 10 11 12 13 public class Solution { public ListNode getIntersectionNode (ListNode headA, ListNode headB) { if (headA==null || headB==null ) return null ; ListNode x=headA, y =headB; while (x!=y) { if (x==null ) x = headB; else x = x.next; if (y==null ) y = headA; else y = y.next; } return x; } }
双指针的比较巧妙应用，利用 $x+y = y+x $的思想，走到底之后还可以重头再走一遍。
环形链表 https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png
1 2 3 4 5 6 7 8 9 10 11 12 public class Solution { public boolean hasCycle (ListNode head) { if (head==null ||head.next==null )return false ; ListNode slow=head, fast=head; while (fast!=null ){ fast = (fast.next==null )?fast.next:fast.next.next; slow = slow.next; if (fast==slow)return true ; } return false ; } }
快慢指针的典型应用，判断链表中是否有环。
环形链表入口节点 https://leetcode.cn/problems/linked-list-cycle-ii/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public class Solution { public ListNode detectCycle (ListNode head) { if (head == null ) return head; ListNode slow = head; ListNode fast = head; while (fast!=null ){ if (fast.next != null ) fast = fast.next.next; else fast = fast.next; slow = slow.next; if (fast == slow) break ; } if (fast == null ) return null ; fast = head; while (fast != slow){ fast = fast.next; slow = slow.next; } return fast; } }
这道题难点在于找出环入口节点。解体的关键在于两个点：
假设head到环入口节点的长度为a，环的长度为len，相遇时距离环入口的偏移为offset
当一个指针走 a + k*len步时，它一定在环入口处
推理：
f = 2*s
s = a + offset + k1*len
f = a + offset + k2*len
得到
即 s 走了整数倍len，f走了整数倍len。
因此只要相遇后，将fast移到头节点，一步一步走再走a步，一定和slow碰面在入口之处。
迭代法（复杂指针操作） 翻转链表 https://leetcode.cn/problems/reverse-linked-list/
(1) 迭代方式反转
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public ListNode reverseList (ListNode head) { ListNode prev = null ; ListNode cur = head; ListNode tmp = null ; while (cur != null ){ tmp = cur.next; cur.next = prev; prev = cur; cur = tmp; } return prev; } }
迭代方式翻转，自然需要两个指针;
需要注意的是翻转前后的尾巴null处理
pre指向已经翻转的链表头节点，初始为null；
cur指向下一个要翻转的节点，初始为head
（2）递归方式反转
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public ListNode reverseList (ListNode head) { if (head==null ) return null ; if (head.next==null ) return head; ListNode prev = reverseList(head.next); head.next.next = head; head.next = null ; return prev; } }
翻转部分链表 https://leetcode.cn/problems/reverse-linked-list-ii/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public ListNode reverseBetween (ListNode head, int left, int right) { ListNode dummyHead = new ListNode (-1 ); dummyHead.next = head; ListNode pre = dummyHead; for (int i=0 ; i<left-1 ; ++i){ pre = pre.next; } ListNode tmp1 = pre; ListNode tmp2 = pre.next; ListNode prev = null ; ListNode curr = pre.next; for (int i=0 ; i<= right-left; ++i){ ListNode tmp = curr.next; curr.next = prev; prev = curr; curr = tmp; } tmp1.next = prev; tmp2.next = curr; return dummyHead.next; } }
反转特定范围内的链表，需要注意边界条件。
两两交换链表节点
迭代方式自然需要保存多个指针，修改互相的引用，然后顺序遍历下去。
为了使得处理更加顺畅，引入虚拟头节点
如果被指针指向的顺序搞懵，不如多声明几个变量，保存节点
两两反转需要两个变量
迭代处理，需要前驱和后继，又要两个变量
总共四个变量
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public ListNode swapPairs (ListNode head) { ListNode dummyHead = new ListNode (-1 ); dummyHead.next = head; ListNode prev = dummyHead; ListNode curr = prev.next; if (curr==null || curr.next==null ) return head; ListNode nest = curr.next; ListNode tmp = nest.next; while (curr!=null ){ nest.next = curr; curr.next = tmp; prev.next = nest; prev = curr; if (prev.next==null ) break ; curr = prev.next; if (curr==null ||curr.next==null ) break ; nest = curr.next; tmp = nest.next; } return dummyHead.next; } }
简洁写法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public ListNode swapPairs (ListNode head) { ListNode dummyHead = new ListNode (-1 ); dummyHead.next = head; ListNode prev = dummyHead; while (prev.next!=null && prev.next.next!=null ){ ListNode curr = prev.next; ListNode nest = curr.next; ListNode tmp = nest.next; nest.next = curr; curr.next = tmp; prev.next = nest; prev = curr; } return dummyHead.next; } }
巧妙递归 翻转部分链表
https://leetcode.cn/problems/reverse-linked-list-ii/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { ListNode reverseN (ListNode head, int N) { if (head==null || N==1 ) return head; ListNode rHead = reverseN(head.next, N-1 ); ListNode tmp = head.next.next; head.next.next = head; head.next = tmp; return rHead; } public ListNode reverseBetween (ListNode head, int left, int right) { if (left == 1 ){ return reverseN(head, right); } ListNode rHead = reverseBetween(head.next, left-1 , right-1 ); head.next = rHead; return head; }
主要思想：将left和right堪称相对于头节点的索引。当left为1时，题目归化为反转开头N个节点。
K个一组翻转链表
https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public ListNode reverseN (ListNode head, int N) { if (N==1 ) return head; ListNode rHead = reverseN(head.next, N-1 ); ListNode tmp = head.next.next; head.next.next = head; head.next = tmp; return rHead; } public ListNode reverseKGroup (ListNode head, int k) { ListNode count = head; for (int i=0 ; i<k; ++i){ if (count!=null ) count = count.next; else return head; } ListNode rHead = reverseN(head, k); head.next = reverseKGroup(head.next, k); return rHead; } }
思想：反转前K个后，第K+1个节点还是一样处理。
两两交换链表中的节点
https://leetcode.cn/problems/swap-nodes-in-pairs/
1 2 3 4 5 6 7 8 9 10 11 class Solution { public ListNode swapPairs (ListNode head) { if (head==null ||head.next==null ) return head; ListNode headNext = head.next; ListNode tmp = swapPairs(headNext.next); headNext.next = head; head.next = tmp; return headNext; } }
其实就是K一组翻转链表，K=2的情形。
判断回文链表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public ListNode left; public boolean isPalindrome (ListNode head) { left = head; return traverse(head); } public boolean traverse (ListNode head) { if (head == null ) return true ; boolean res = traverse(head.next); if (left.val != head.val) return false ; left = left.next; return res; } }
这个写法比较邪门，将链表想象成一颗退化的树，借助left存储最左端的点，递归一直到最右端，然后判断左右是否相等。
合并链表 合并两个有序链表 https://leetcode.cn/problems/merge-two-sorted-lists
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public ListNode mergeTwoLists (ListNode list1, ListNode list2) { if (list1==null ) return list2; if (list2==null ) return list1; ListNode dummyHead = new ListNode (-1 ); ListNode op = dummyHead; while (list1!=null && list2!=null ){ ListNode tmp = new ListNode (-1 ); if (list1.val < list2.val){ tmp.val = list1.val; list1 = list1.next; }else { tmp.val = list2.val; list2 = list2.next; } op.next = tmp; op = op.next; } if (list1!=null ) op.next =list1; if (list2!=null ) op.next =list2; return dummyHead.next; } }
合并K个有序链表 https://leetcode.cn/problems/vvXgSW/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public ListNode meregeTowListInplace (ListNode head1, ListNode head2) { ListNode op1 = head1; ListNode op2 = head2; ListNode dummyHead = new ListNode (-1 ); ListNode op3 = dummyHead; while (op1!=null && op2!=null ){ if (op1.val < op2.val){ op3.next = op1; op1=op1.next; }else { op3.next = op2; op2=op2.next; } op3 = op3.next; } if (op1!=null ) op3.next = op1; if (op2!=null ) op3.next = op2; return dummyHead.next; } public ListNode MergeSort (ListNode[] lists, int start, int end) { if (start>=end) return lists[start]; int mid = (end-start)/2 + start; ListNode head1 = MergeSort(lists, start, mid); ListNode head2 = MergeSort(lists, mid+1 , end); return meregeTowListInplace(head1, head2); } public ListNode mergeKLists (ListNode[] lists) { if (lists.length==0 ) return null ; return MergeSort(lists, 0 , lists.length-1 ); } }
链表合并，天然适合二路归并算法。 合并两条链表算法很简单，并且原地操作。合并2条链表后，可以再合并4条链表，8条链条，最终合并全部链表！
解法二：堆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public ListNode mergeKLists (ListNode[] lists) { if (lists == null || lists.length == 0 ) return null ; PriorityQueue<ListNode> pq = new PriorityQueue <>(lists.length, new Comparator <ListNode>() { @Override public int compare (ListNode o1, ListNode o2) { if (o1.val < o2.val) return -1 ; else if (o1.val == o2.val) return 0 ; else return 1 ; } }); for (ListNode node: lists){ if (node!=null ) pq.offer(node); } ListNode dummyHead = new ListNode (-1 ); ListNode op = dummyHead; while (!pq.isEmpty()){ op.next = pq.poll(); op = op.next; if (op.next!=null ) pq.add(op.next); } return dummyHead.next; } }
想清楚操作的顺序，再写代码，不然逻辑混乱，越改越错！
算法思想：K个升序链表，每次我们都要取最小的。利用升序的特性，我们可以知道最小元素只在每个链表的头部产生。
这个过程抽象为从一个候选集合中取最小值，自然想到堆数据结构。
算法步骤：
1、先取K个链表头部元素建立堆；
2、从堆中取一个，那下一个最小的元素，只可能从取中节点所在的链表产生。所以从那个链表头部取一个节点。
3、不断取一个补一个，最后再将堆中的元素全部取出的即可。
排序链表 https://leetcode.cn/problems/sort-list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { public ListNode meregeTowListInplace (ListNode head1, ListNode head2) { ListNode op1 = head1; ListNode op2 = head2; ListNode dummyHead = new ListNode (-1 ); ListNode op3 = dummyHead; while (op1!=null && op2!=null ){ if (op1.val < op2.val){ op3.next = op1; op1=op1.next; }else { op3.next = op2; op2=op2.next; } op3 = op3.next; } if (op1!=null ) op3.next = op1; if (op2!=null ) op3.next = op2; return dummyHead.next; } public ListNode mergeSort (ListNode head) { if (head==null ||head.next==null ) return head; ListNode slow = head, fast =head.next; while (fast!=null && fast.next!=null ){ fast = fast.next.next; slow = slow.next; } ListNode secondHead = slow.next; slow.next=null ; ListNode head1 = mergeSort(head); ListNode head2 = mergeSort(secondHead); return meregeTowListInplace(head1, head2); } public ListNode sortList (ListNode head) { return mergeSort(head); } }
重排链表 https://leetcode.cn/problems/reorder-list/description/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public ListNode reverse (ListNode head) { if (head==null || head.next ==null ) return head; ListNode tmp = reverse(head.next); head.next.next = head; head.next =null ; return tmp; } public void reorderList (ListNode head) { if (head==null || head.next ==null ) return ; ListNode slow = head; ListNode fast = head.next; while (fast!=null && fast.next!=null ){ slow = slow.next; fast = fast.next.next; } ListNode head2 = reverse(slow.next); slow.next =null ; ListNode head1 = head; while (head2!=null ){ ListNode tmp1 = head1.next; ListNode tmp2 = head2.next; head1.next = head2; head2.next = tmp1; head1 = tmp1; head2 = tmp2; } return ; } }
技术细节：快慢指针+反转链表
其他 判断回文链表 https://leetcode.cn/problems/palindrome-linked-list/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public ListNode reverseList (ListNode head) { if (head==null || head.next==null ) return head; ListNode tmp = reverseList(head.next); head.next.next = head; head.next =null ; return tmp; } public boolean isPalindrome (ListNode head) { if (head==null || head.next==null ) return true ; ListNode slow = head, fast = head; while (fast!=null && fast.next!=null ){ fast = (fast.next==null )? fast.next:fast.next.next; slow = slow.next; } ListNode LastHalfNode = reverseList(slow); while (LastHalfNode!=null && head!=null ){ if (LastHalfNode.val != head.val){ return false ; } LastHalfNode = LastHalfNode.next; head = head.next; } return true ; } }
暴力的做法是开辟额外空间存储遍历后数组的值，再用双指针前后夹击判断。思考空间复杂读O（1）的算法，自然的想法是翻转一半的链表，然后比较两条链表。
（1）获取中间节点
方法是快慢指针。问题来了，奇数长度中间节点是确定的，偶数长度链表的中间节点是哪一个？答案是取决于快慢指针的具体实现，有可能是前一半的最后一个节点，也有可能是后一半的第一个节点。
1 2 3 4 5 ListNode slow = head, fast = head;while (fast!=null && fast.next!=null ){ fast = (fast.next==null )? fast.next:fast.next.next; slow = slow.next; }
（2）偷懒的一个技巧
直接比较两条链表，不比较长度，奇数长度情况下最后一个节点不会被比较。
升序矩阵寻找第K个大小的元素 https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/description/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { class Status implements Comparable <Status>{ public int val; public int x; public int y; Status(int val, int x, int y){ this .val = val; this .x = x; this .y = y; } @Override public int compareTo (Status st) { if (this .val < st.val) return -1 ; if (this .val > st.val) return 1 ; return 0 ; } } public int kthSmallest (int [][] matrix, int k) { PriorityQueue<Status> pq = new PriorityQueue <>(); int N = matrix.length; for (int i=0 ; i<N; ++i) pq.offer(new Status (matrix[i][0 ], i, 0 )); while (k>1 ){ Status st = pq.poll(); if (st.y < N-1 ){ int new_x = st.x; int new_y = st.y+1 ; pq.offer(new Status (matrix[new_x][new_y], new_x, new_y)); } k--; } Status st = pq.poll(); return st.val; } }
这道题的思想和合并K个升序链表一摸一样。但是忽略了列间的单调上升关系。
