链表题总结

链表这种数据结构，解题的时候空间复杂度往往是 O(1)

关于 dummy node

有时候，解法中需要设置一个 dummy 节点，指向 head：

1	const dummy: ListNode = { val: 0, next: head };

这种技巧在 head 节点有可能被删除或更改的情况下会很有用。

关于循环终止条件的设置

下面这两种终止条件都是很常见的：

1
2
3

while (currentNode.next) {
// ...
  }

1
2
3

while (currentNode) {
// ...
  }

区别在于，如果终止条件设置成 currentNode ，那么 currentNode 最终会停在 null ，这确保了你循环里的操作会作用于完整的所有节点。

而 currentNode.next 则是会作用到链表的最后一个节点的前一个节点。这在你会对当前节点的下一个节点进行操作的时候会很有用。

关于中间节点

一种常见的找中间节点的算法（Leetcode 876 题）：

核心是快慢指针，快指针每次走两步，慢指针则会是一步。

function middleNode(head: ListNode | null): ListNode | null {
  let slow = head,
    fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast!.next.next;
  }
  return slow;
}

这种算法中，slow 指针最后会停在中间的那个节点，亦或者中间偏后的那个节点（在节点个数是偶数时）。

关于反转链表

一种经典的反转链表的算法：

function reverseList(head: ListNode) {
  let preNode: ListNode | null = null,
    currentNode: ListNode | null = head;
  while (currentNode) {
    const nextNode = currentNode.next;
    currentNode.next = preNode;
    preNode = currentNode;
    currentNode = nextNode;
  }
  return preNode;
}

这种算法通常需要一个 nextNode 来缓存中间结果。
前一个节点一般初始化为 null
由于循环终止条件是 currentNode ，最后 preNode 才会变成链表的头节点。

解决某些题的时候（如回文链表和重排链表，需要同时用到反转算法和中间节点算法）

关于链表中的环

判断是否有环？

Leetcode 142.

两个指针从头开始同时出发，快指针每次走 2 步，慢指针则是 1 步。

如果有环的话，快指针最终总会追上慢指针，亦或者总它后面：

1	if (fast.next === slow \|\| fast.next.next === slow) return true;

找环的出现位置？

Leetcode 142.

需要用到 Floyd 判圈算法 。

还是让快慢指针同时出发，不过我们可以通过一些数学技巧得出：

快慢指针相遇的时候，慢指针距离环的入口的距离，总是等于 head 到环的入口的距离

所以，当快慢指针相遇的时候，我们让慢指针和 head 指针同时出发，两者相遇的位置，则是环的入口节点。

不过值得一提的是，从相遇点到入口点，虽然图中看起来像是只经过了不到一圈，不过实际上可能会经过更多圈。

每 k 个一组翻转链表

Leetcode 25.

例如：

* 输入：head = [1,2,3,4,5], k = 2

* 输出：[2,1,4,3,5]

这题麻烦的点在于，得搞清楚指针到底往哪里指，指向谁。所以还是蛮考验功底的。

我们需要先统计链表总节点个数，因为只有这样才能知道循环需要进行几次：

假设统计出链表节点个数为 n ：

1	for (let i = 0; i < Math.floor(n / k); i++)

然后在内层，我们需要进行一次上文的反转链表算法，这不难，难的是在这之后我们需要手动修复指针：

//   k 个 1 组，进行几组？
for (let i = 0; i < Math.floor(n / k); i++) {
  for (let j = 0; j < k; j++) {
    const nextNode = currentNode!.next;
    currentNode!.next = prevNode;
    prevNode = currentNode;
    currentNode = nextNode;
  }
  const nextNode = p0.next;
  p0.next!.next = currentNode;
  p0.next = prevNode;
  p0 = nextNode!;
}

最后，由于头节点也会被反转，所以我们需要一个 dummy node ，这个上文已经提及了。

脑筋急转弯

还有一些需要一点点技巧和智慧的处理，比如：

删除链表中的某个节点，但是不给头节点

这种情况我们思路打开，依次把要删除的节点之后的值前移即可。

删除链表中的倒数第 N 个节点

幻想出一把长度固定为 n 的尺在链表中游走，利用快慢指针，我们把倒数转化为正数

Leaves' blog