通常链表操作指针操作，可能还不止一个，还要防止被边界条件坑一下，其实，这种费力不讨好的操作，可以被 递归 替代，递归本的质是暴力穷举，算不上算法，只能是编码的实现方式。对电脑来说，两者都是要求它老老实实干活，但是 递归 对于人脑更好理解。

一. 基础操作

0.快慢指针 正确性证明

快慢指针是一种常见的解法，但是我对快慢指针总是不相信：在连续的世界快慢指针一定会相遇，但是在离散世界是有可能永远不会相遇的。

这里有证明：
https://zhuanlan.zhihu.com/p/60736361
image.png
<线性同余方程 >
是数学定理，他说 当 快指针步长为2，慢指针步长为1时，不管圈大小，起点如何都会追上！这里不在细究，但是终于相信。

1. 由数组生成链表

1）递归生成，代码更简单

  1. function ListNode(val, next) {
  2.     this.val = (val === undefined ? 0 : val)
  3.     this.next = (next === undefined ? null : next)
  4. }
  6. function getListFromArray(arr) {
  7.     if (!arr.length) {
  8.         return null;
  9.     }
  11.     const head = new ListNode(arr.shift());
  12.     head.next = getListFromArray(arr);
  14.     return head;
  15. }

2）常规生成

dumyHead 的漂亮亮相

  1. function ListNode(val, next) {
  2.     this.val = (val===undefined ? 0 : val)
  3.     this.next = (next===undefined ? null : next)
  4. }
  5. function List(nums) {
  6.     if (nums.length === 0) {
  7.         return null;
  8.     }
  10.     let dumyHead = new ListNode();
  11.     let p = dumyHead;
  12.     for (let num of nums) {
  13.         let cur = new ListNode(num, null);
  14.         p.next = cur;
  15.         p = p.next;
  16.     }
  18.     return dumyHead.next;
  19. }
  21. new List([4,2,1,3])；

如果不用 dummyhead 就会很繁琐，代码也不好理解：

  1. function List(nums) {
  2.     if (nums.length === 0) {
  3.         return null;
  4.     }
  6.     let head;
  7.     let pre;
  8.     for (let num of nums) {
  9.         let cur = new ListNode(num, null);
  10.         if (!pre) {
  11.             head = cur;
  12.             pre = cur;
  13.         } else {
  14.             pre.next = cur;
  15.             pre = cur;
  16.         }
  17.     }
  19.     return head;
  20. }

2. 翻转链表

剑指 Offer 24. 反转链表

抛开繁琐的而且很容错的指针操作，用 递归 简直清爽太多了。

  1. function reverseList(head) {
  2.     function recur(head, pre) {
  3.         if (head === null) {
  4.             return pre;
  5.         }
  6.         let newHead = recur(head.next, head);
  7.         head.next = pre; // head 是逆转之后链表的尾部
  9.         return newHead;
  10.     }
  12.     return recur(head, null);
  13. }

25. K 个一组翻转链表

在 24 翻转链表的基础上：

  1. var reverseKGroup = function(head, k) {
  3.     function reverseList(head) {
  4.         if (!head) {
  5.             return null;
  6.         }
  8.         let p = head;
  9.         for (let i = 1; i < k; i++) {
  10.             if (p.next) {
  11.                 p = p.next
  12.             } else { // 不够k个，原样返回
  13.                 return head;
  14.             }
  15.         }
  16.         let nextHead = p.next;
  17.         p.next = null;
  19.         let [_head, _tail] = _reverseList(head);
  21.         _tail.next = reverseList(nextHead);
  23.         return _head;
  24.     };
  26.     return reverseList(head);
  27. };
  29. function _reverseList(head) {
  31.     function recur(head, pre) {
  32.         if (head === null) {
  33.             return pre;
  34.         }
  35.         let _newHead = recur(head.next, head);
  36.         head.next = pre; // head 是逆转之后链表的尾部
  38.         return _newHead;
  39.     }
  41.     let newHead = recur(head, null);
  42.     return [newHead, head];
  43. }

删除元素

83. 删除排序链表中的重复元素

还是使用 递归的方式去做，安全而保险

  1. var deleteDuplicates = function(head) {
  2.     function dfs(node) {
  3.         if (!node) {
  4.             return;
  5.         }
  6.         while (node.next && (node.val === node.next.val)) { // 前序操作！！
  7.             node.next = node.next.next;
  8.         }
  9.         dfs(node.next);
  10.     }
  12.     dfs(head);
  14.     return head;
  15. };

而使用传统指针就麻烦多了。

  1. var deleteDuplicates = function(head) {
  2.     if (!head || !head.next) {
  3.         return head;
  4.     }
  6.     let p = head;
  7.     while(p && p.next) { // 不知道要循环多少次，就用 while
  8.         if (p.val === p.next.val) { // 有重复就删除
  9.             p.next = p.next.next;
  10.         } else { // else 特别关键，只有不同时，才移动指针，否则一直比
  11.             p = p.next;
  12.         }
  13.     }
  15.     return head;
  16. };

82. 删除排序链表中的重复元素 II

感觉细节太多了：要区分是否有重复区间，有就要删除

  1. var deleteDuplicates = function(head) {
  2.     let dummyHead = new ListNode(); // 安装假头，以防第一个元素就是重复元素
  3.     dummyHead.next = head;
  5.     let q = dummyHead;
  6.     let p = head;
  7.     let toDelete = false;
  8.     while (p && p.next) {
  10.         while (p.next && p.val === p.next.val) {
  11.             toDelete = true;
  12.             p = p.next;
  13.         }
  15.         if (toDelete) {
  16.             q.next = p.next;
  17.             p = p.next; // 一开始丢了这个
  18.             toDelete = false;
  19.         } else {
  20.             q = p;
  21.             p = p.next;
  22.         }
  23.     }
  25.     return dummyHead.next;
  26. };

上面是引入了第三方变量，其实还有一种方式：

  1. var deleteDuplicates = function(head) {
  2.     let dummyHead = new ListNode(); // 安装假头，以防第一个元素就是重复元素
  3.     dummyHead.next = head;
  5.     let q = dummyHead;
  6.     let p = head;
  8.     while (p && p.next) {
  10.         while (p.next && p.val === p.next.val) { // 跳出 while 循环时，p指向最后一个重复元素
  11.             p = p.next;
  12.         }
  14.         // if (toDelete) {
  15.         if (q.next !== p) { // p 有移动过，代表有重复元素
  16.             q.next = p.next;
  17.             p = p.next; // 一开始丢了这个
  18.             // toDelete = false;
  19.         } else {
  20.             q = p;
  21.             p = p.next;
  22.         }
  23.     }
  25.     return dummyHead.next;
  26. };

其实指针操作极其容易出错，其实可以使用递归的操作：(很棒！)
同样要区分是否有 重复区间：

  1. var deleteDuplicates = function(head) {
  2.     if (!head) {
  3.         return null;
  4.     }
  6.     let dummyHead = new ListNode(); // 安装假头，以防第一个元素就是重复元素
  7.     dummyHead.next = head;
  9.     if (head.next && (head.val === head.next.val)) {
  10.         while (head.next && (head.val === head.next.val)) {
  11.             head = head.next;
  12.         }
  13.         dummyHead.next = deleteDuplicates(head.next); // 处理1
  14.     } else {
  15.         head.next = deleteDuplicates(head.next); // 处理2
  16.     }
  19.     return dummyHead.next;
  20. };

合并链表

合并两个有序链表

递归写法：（很简洁）

  1. function mergeTwoList(l1, l2) {
  2.     if (!(l1 && l2)) {
  3.         return l1 || l2;
  4.     }
  6.     if (l1.val < l2.val) {
  7.         l1.next = mergeTwoList(l1.next, l2);
  8.         return l1;
  9.     } else {
  10.         l2.next = mergeTwoList(l1, l2.next);
  11.         return l2;
  12.     }
  13. }

对比一般写法：（很复杂，容易错）

  1. function mergeTwoList(l1, l2) { // 合并 lists 的套路：一个 while 循环，加四个 if 条件
  2.     const dummyHead = new ListNode();
  3.     let p = dummyHead;
  5.     while (l1 || l2) { // 两个链表还没遍历完
  6.         if (l1 && l2) {
  7.             if (l1.val < l2.val) {
  8.                 p.next = l1;
  9.                 l1 = l1.next;
  10.             } else {
  11.                 p.next = l2;
  12.                 l2 = l2.next
  13.             }
  14.         } else if (l1 && !l2) {
  15.             p.next = l1;
  16.             l1 = l1.next;
  17.         } else if (!l1 && l2) {
  18.             p.next = l2;
  19.             l2 = l2.next;
  20.         }
  21.         p = p.next;
  22.     }
  24.     p = null; // 结尾
  26.     return dummyHead.next;
  27. }

23. 合并K个升序链表

  1. var mergeKLists = function(lists) {
  2.     let n = lists.length;
  3.     if (n === 1) {
  4.         return lists[0]
  5.     }
  6.     if (n === 0) {
  7.         return null;
  8.     }
  10.     const finalList = lists.reduce((pre, cur) => mergeTwoList(pre, cur));
  12.     return finalList;
  13. };

148. Sort List

image.png
归并排序的基调定下来之后
1）先使用快慢指针把 链表分成两部分
2）然后递归，最后知道链表长度 <= 1 即可
3）归并

  1. var sortList = function(head) {
  2.     if (!head) {
  3.         return null;
  4.     }
  5.     if (!head.next) {
  6.         return head;
  7.     }
  9.     let slow = head;
  10.     let fast = head.next;
  12.     while (fast) {
  13.         if (!fast.next) {
  14.             break;
  15.         }
  17.         slow = slow.next;
  18.         fast = fast.next.next;
  19.     }
  21.     let l2 = slow.next
  22.     slow.next = null;
  23.     let l1 = head;
  25.     l1 = sortList(l1);
  26.     l2 = sortList(l2)
  28.     return mergeTwoList(l1, l2);
  29. };

结果还可以：
image.png
代码写了一大坨，感觉很冗长。

二、else

2. 两数相加

  1. var addTwoNumbers = function(l1, l2) {
  2.     let head = new ListNode(0); // 假头
  3.     let p = head;
  4.     let p1 = l1;
  5.     let p2 = l2;
  7.     let carry = 0;
  8.     while (p1 || p2 || carry) {
  9.         sum = (p1 ? p1.val : 0) + (p2 ? p2.val : 0) + carry;
  10.         carry = (sum >= 10) ? 1 : 0;
  11.         sum = sum % 10;
  13.         // 有了假头，才能串联的经典操作
  14.         p.next = new ListNode(sum);
  15.         p = p.next;
  17.         p1 = p1 ? p1.next : null;
  18.         p2 = p2 ? p2.next : null;
  19.     }
  21.     return head.next;
  22. };

24. 两两交换链表中的节点

链表操作，指针很多，边界值要考虑清楚。

  1. var swapPairs = function(head) {
  2.     if (!head || !head.next) {
  3.         return head;
  4.     }
  5.     let dummyHead = new ListNode();
  6.     dummyHead.next = head;
  8.     let parent = dummyHead;
  9.     let p1 = parent.next;
  10.     let p2 = p1 ? p1.next : null;
  11.     let child = p2 ? p2.next : null;
  13.     while (p1 && p2) {
  14.         parent.next = p2;
  15.         p2.next = p1;
  16.         p1.next = child;
  18.         parent = p1;
  19.         p1 = child;
  20.         p2 = p1 ? p1.next : null;
  21.         child = p2 ? p2.next : null;
  22.     }
  24.     return dummyHead.next;
  25. };

剑指 Offer 22. 链表中倒数第k个节点

总结 while 循环的写法：

  1. var getKthFromEnd = function(head, k) { // 链表就是过河的卒子不能后退
  2.     let p = head;
  3.     let q = p;
  4.     while ((k - 1) && p) { // 多保护条件
  5.         p = p.next;
  6.         k--;
  7.     }
  9.     while (p && p.next) { // 指针在移动时，临界退出是否指向最后一个？？
  10.         q = q.next;
  11.         p = p.next
  12.     }
  14.     return q;
  15. };

image.png
这样p指向尾部null时，q 会错过它原来的节点。
解决方式很简单，一开始P 和 q 拉的距离加1就行了。
image.png

86. 分隔链表

拼接链表，注意老链表关系的终结。

  1. var partition = function(head, x) {
  2.     let smallList = new ListNode();
  3.     let bigList = new ListNode();
  5.     let smallHead = smallList;
  6.     let bigHead = bigList;
  8.     while (head) {
  9.         if (head.val < x) {
  10.             smallHead.next = head;
  11.             smallHead = smallHead.next;
  12.         } else {
  13.             bigHead.next = head;
  14.             bigHead = bigHead.next;
  15.         }
  16.         head = head.next;
  17.     }
  18.     bigHead.next = null; // 堵上漏洞，这个 next 指向原来链表某个节点，会在新链表中构成环
  19.     smallHead.next = bigList.next;
  21.     return smallList.next;
  22. };

138. 复制带随机指针的链表

1）机械的做法：
两次遍历：第一次，记录老节点和新节点的映射，第二次遍历，将老节点的社会关系告诉新节点

  1. var copyRandomList = function(head) { // 忽略了map这种结构，可以以object为key
  2.     if (head === null) {
  3.         return null;
  4.     }
  6.     const cachedNode = new Map();
  7.     let p = head;
  8.     let p_copy = null;
  9.     while(p) {
  10.         p_copy = new ListNode(p.val);
  11.         cachedNode.set(p, p_copy);
  12.         p = p.next;
  13.     }
  15.     // let new_head = null;
  16.     p = head;
  17.     p_copy = null;
  18.     while (p) {
  19.         p_copy = cachedNode.get(p);
  20.         p_copy.next = p.next ? cachedNode.get(p.next) : null; // 这里有问题
  21.         p_copy.random = p.random ? cachedNode.get(p.random) : null;
  23.         p = p.next;
  24.         // if (!new_head) {
  25.         //     new_head = p_copy;
  26.         // }
  27.     }
  29.     // return new_head;
  30.     return cachedNode.get(head);  // 这个取法很巧妙
  31. }

2）递归算法
很简单，也使用map作为已经完成复制的记录，不断递归（复制节点值，以及关系）

  1. var copyRandomList = function(head, cachedNodeMap = new Map()) { // 忽略了map这种结构，可以以object为key
  2.     if (head === null) {
  3.         return null;
  4.     }
  6.     if (!cachedNodeMap.get(head)) { // 没有被复制过
  7.         let copy = new ListNode(head.val);
  8.         cachedNodeMap.set(head, copy); // 先设置，这很关键
  9.         copy.next = copyRandomList(head.next, cachedNodeMap);
  10.         copy.random = copyRandomList(head.random, cachedNodeMap);
  11.     }
  13.     // p.next = head.next ? new ListNode(head.next) : null;
  14.     // p.random = head.random ? new ListNode(head.random) : null;
  16.     return cachedNodeMap.get(head);
  17. }

对于递归算法，我一开始不放心的是会不会遍历链表全部的问题。其实，由于 当前指针 p 有 两个 指向：p.next 和 p.random，p.random 乱指虽然不保证全部遍历，但是 p.next 一定会保证的！

1485. 克隆含随机指针的二叉树

和 138 一样的解题思路

  1. var copyRandomBinaryTree = function(root) {
  2.     let visitedMap = new Map();
  4.     function dfs(node) { // 递归返回的是 复制后的node
  5.         if (!node) {
  6.             return node;
  7.         }
  9.         // 先序操作
  10.         if (visitedMap.has(node)) {
  11.             return visitedMap.get(node);
  12.         }
  13.         const newNode = new NodeCopy(node.val); // 题意要求新 class
  14.         visitedMap.set(node, newNode); // 顺序放在这里才对
  16.         // 这个三个大哥的顺序无所谓。
  17.         newNode.left = dfs(node.left);
  18.         newNode.random = dfs(node.random);
  19.         newNode.right = dfs(node.right);
  21.         // visitedMap.set(node, newNode);
  23.         return newNode;
  24.     }
  26.     return dfs(root);
  27. };

三、需要记忆的特殊题目

160. 相交链表

image.png
image.png

相交链表 和 平行链表的区别：
平行链表，在各自链表被遍历到末尾时，折回另一个链表的头部返回折时，不会相交。
image.png

  1. var getIntersectionNode = function(headA, headB) {
  2.     if (!(headA && headB)) { // 有一个为空链表，则不相交
  3.         return null;
  4.     }
  6.     let pA = headA;
  7.     let pB = headB;
  9.     let pA_switched = false;
  10.     let pB_switched = false;
  11.     while (pA !== pB) {
  12.         if (pA_switched && pB_switched) {
  13.             pA = pA.next;
  14.             pB = pB.next;
  16.             if (!pA && !pB) {
  17.                 return null;
  18.             }
  19.             continue;
  20.         }
  22.         if (pA.next) {
  23.             pA = pA.next;
  24.         } else {
  25.             // pA = headB;
  26.             if (!pA_switched) {
  27.                 pA = headB;
  28.                 pA_switched = true;
  29.             }
  30.         }
  32.         if (pB.next) {
  33.             pB = pB.next;
  34.         } else {
  35.             // pB = headA;
  36.             if (!pB_switched) {
  37.                 pB = headA;
  38.                 pB_switched = true;
  39.             }
  40.         }
  41.     }
  43.     return pA;
  44. };

我这写的很复杂，但是现实中，我可能就写成这个球像了。
image.png
上面冗长的代码，都是没有考虑到下面这一点，不相交的链表，交换方向都指向末尾 null 时，可以终止 while 循环:
image.png
因此，也无需考虑是否交换过方向：

  1. var getIntersectionNode = function(headA, headB) {
  2.     if (!(headA && headB)) { // 有一个为空链表，则不相交
  3.         return null;
  4.     }
  6.     let pA = headA;
  7.     let pB = headB;
  9.     while (pA !== pB) { // 不会陷入死循环：如果两条链平行的话，pa pb 都是null，会跳出while
  10.         if (pA) {
  11.             pA = pA.next;
  12.         } else {
  13.             pA = headB;
  14.         }
  16.         if (pB) {
  17.             pB = pB.next;
  18.         } else {
  19.             pB = headA;
  20.         }
  21.     }
  23.     return pA;
  24. };

上述解法，有一种情况被掩盖了：
那就是 两个相交列表，在第一次遍历就完成结果了。

142. 环形链表 II

找环的节点

https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/
image.png
上面的等式能看出来是什么意思？能看出来吗？下面是结论：
image.png