链表
# 链表
链表是一种重要的数据结构，能够在O(1)时间内添加或删除节点，但是访问节点需要O(n)。
为了简化链表的头部节点操作，一般给链表添加一个哨兵节点（或哑结点）。
链表相关的算法中，首先需要了解Floyd判圈算法，了解相关原理，学会使用快慢指针。
由于链表的指向性结构，在链表中也可使用递归，即可形成正反两个方向的扫描。
最后还要了解几个链表相关的经典问题。
本文是对力扣-链表专题 (opens new window)的总结。
# 哨兵节点
对于链表的添加或删除操作，正常都需要对头结点进行额外的判断。为了简化判断，使其对头部节点的操作与其他节点报纸一直，可增加哨兵节点。
哨兵节点不保存任何数据，只是用作伪头、伪尾，用于简化边界判断。
在单链表中增加伪头，在双链表中增加伪头、伪尾。
// 哨兵节点示例
function addNode(head, val) {
// 无哨兵节点时，添加一个节点
{
// 需要判断头结点是否存在
const node = new ListNode(val);
if (!head) return node;
let p = head;
while (p && p.next) {
p = p.next;
}
p.next = node;
return head;
}
// 有哨兵节点时，添加一个节点
{
// 创建哨兵节点
const dummy = new ListNode(0);
dummy.next = head;
// add，统一节点操作，简化边界判断情况
const node = new ListNode(val);
let p = dummy;
while (p && p.next) {
p = p.next;
}
p.next = node;
return dummy.next;
}
}
// 创建哨兵节点示例
// 对单链表创建头部哨兵节点，即伪头（也称哑节点）
const dummy = new ListNode(0);
dummy.next = head;
return dummy.next;
# Floyd判圈算法
Floyd判圈算法也称为快慢指针，是一个可以在有限状态机、迭代函数或者链表上判断是否存在环，求出该环的起点与长度的算法。即通过该算法可解决以下三个问题：
- 判断是否存在环
- 求出环的起点
- 求出环的长度、入环前的长度
下面先给出这三个问题的求解方法，最后给出Floyd判圈算法的证明，一定要对该证明理解，然后才能掌握Floyd判圈算法，熟练的使用快慢指针解决链表的相关问题。
# 判断是否存在环
Q：给出一个链表头结点，判断是否存在环。
A：使用快慢指针，快指针一次走两步，慢指针一次走一步，如果快慢指针能够再次相遇，则说明有环，反之则无环。
// js代码
if (!head) return false;
let slow = head;
let fast = head;
while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
// 再次相遇则说明有环
if (slow == fast) return true;
}
return false;
# 求出环的起点
Q：给出一个链表头结点，如果链表有环，则返回入环的第一个节点；如果无环，则返回null
A：使用快慢指针，先判断是否存在环。如果存在环，则将快指针指向头结点，然后快慢指针每次都各走一步，再次相遇的节点，就是入环的第一个节点。
// js代码
if (!head) return null;
// 先使用快慢指针判断是否存在环
let slow = head;
let fast = head;
while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
// 存在环，则找环的开始点
if (fast == slow) {
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
// 再次相遇的节点就是入环的第一个节点
// 注意：该判断不能写到while里，因为有可能头结点就是入环的第一个节点
if (fast == slow) return fast;
}
}
return null;
# 求出环长和入环前的长度
Q：给出链表的头结点，假设该链表存在环，求出环长和入环前的长度。
A：使用快慢指针，当快慢指针相遇时：
- 计算环长，使快指针暂停，慢指针继续走，并计数，当再次相遇时，慢指针走的周长即环长；
- 计算入环前长度，使快指针指向头结点，快慢指针每次各走一步，当快慢指针再次相遇时，快指针走的步数即为入环前的长度。
# Floyd判圈算法证明
完全理解Floyd判圈算法是必要的，理解后才能比较容易记住，下面给出该算法的简单证明。
设定hare的移动速度是tortoise的 2 倍，起始点到环的入口的距离是T，环的长度是C:
- 当
tortoise第一次走到环入口StartPoint时位置为t1，其走过的距离为T；hare的位置为h1，此时距离StartPoint右侧距离为r，左侧距离为C - r。由于hare的移动速度是tortoise的 2 倍，可得T + r + k*C= 2T，即T = r + kC,k >= 0 - 假设
tortoise停止移动，当hare追上tortoise时，hare移动的距离为C - r。但是hare移动时，tortoise也在移动，当tortoise与hare在h2/t2点相遇时（meet point），假设tortoise移动的距离为x，则有C - r + x = 2x，即x = C - r，即tortoise移动的距离为C - r，即meet point距离start point左侧距离为 C- r，右侧距离为r - 把
hare放回到起点，此时hare和tortoise以同样的速度移动，则由于T = r + kC,k >= 0，则hare与tortoise再次相遇时，一定在entry point，同时hare移动的距离就为T的距离 - 从第2步开始，当
hare与tortoise相遇后，使hare停止移动，让tortoise继续移动，则再次相遇时，tortoise移动的距离即为环长C
# 引申
注意，Floyd判圈算法不只是对链表适用，类似可抽象为求环的问题都可以考虑使用。
- 202. 快乐数 (opens new window)，该题即可抽象为求环问题，因此也可使用快慢指针解决。
# 快慢指针寻找节点
# 快慢指针寻找倒数第N个节点
这里介绍快慢指针对寻找倒数第N个节点的应用，或者称为先后指针，即让一个指针先移动N步，然后再以同样的速度同时移动两个指针，当快指针走到指针末尾null时，慢指针即指向第n个元素。
Q：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
A：利用快慢指针，或称先后指针。快慢指针从哨兵节点开始，快指针提前走n步，此时快慢指针之间间隔n-1步，然后快慢指针一起走，当快指针走到链表尾部的最后一个节点的时候，慢指针指向的就是第n个元素的前驱节点（即倒数第n+1个元素），则可以直接删除第n个节点slow.next = slow.next.next
// 创建哨兵节点，简化操作
const dummy = new ListNode(0);
dummy.next = head;
// 快慢指针均从哨兵节点开始
let slow = dummy;
let fast = dummy;
// 快指针提前走n步，这时快指针快n个节点
for (let i = 0; i < n; i++) {
fast = fast.next;
}
// 然后快慢指针一起走，当快指针走到链表最后一个节点时，慢指针指向倒数第 n个元素 的前驱节点（第n+1个节点）
while (fast && fast.next) {
fast = fast.next;
slow = slow.next;
}
// 对第n个节点进行删除，由于哨兵节点的存在，无需对头结点的特殊情况做判断
slow.next = slow.next && slow.next.next;
return dummy.next;
# 快慢指针寻找中间节点
对于快指针速度是慢指针速度两倍的情况下，快指针移动到末尾时，慢指针即指向中间节点。
Q：给一个链表，寻找链表的中间节点，如果链表节点为偶数，则返回第二个节点
A：利用快慢指针，快指针一次走两步，慢指针一次走一步，当快指针走向链表结尾null时，则慢指针指向中间节点（奇数时为中间节点，偶数时为第二个节点）
var middleNode = function (head) {
// 创建哨兵节点
const dummy = new ListNode(0, head);
let slow = dummy;
let fast = dummy;
// fast 需要走到链表末尾，即 fast = null 时，才能确保 slow 指向中间节点（靠后的中间节点，即偶数时取后）
while (fast) {
slow = slow.next;
// 注意这里判断，fast为最后一个元素时，则fast.next = null；为倒数第二个元素是，fast.next.next = null
fast = fast.next && fast.next.next;
}
// 最终慢指针指向的就是中间节点
return slow;
};
# 链表中递归
单链表的特性是只能单方向遍历，但是可以利用递归，对其进行正反两个方向的遍历。
其实递归就是自动维护了一个栈，用迭代的方式就是遍历链表时，节点入栈，链表遍历结束，节点出栈，形成正反两个方向的节点遍历。
Q：判断一个链表是否是回文链表。
A：维护一个头结点，使用递归到尾部，然后对其进行正反两个方向的扫描对比。
var isPalindrome = function (head) {
if (!head) return false;
// 维护一个全局首指针
let front = head;
// 递归，形成反方向的指针
const recursive = (node) => {
// 递归结束条件，到链表尾部，返回后开始正反两方向的对比
if (!node) return true;
// 形成递归，有一处对比失败，则直接返回false
if (!recursive(node.next)) return false;
// 正反两方向进行对比
if (front.val != node.val) return false;
// 头指针后移，正方向的移动
front = front.next;
return true;
};
return recursive(head);
};
# 链表经典问题
链表中还有其他几个经典的问题
- 相交链表
- 反转链表
# 相交链表
Q：给两个单链表的头指针headA和headB，找出相交的起始节点，如果不相交则返回null
A：一个思路是利用Floyd算法造环判断，但是还有一个更好的算法是利用双指针，使pA和pB两个指针走过的路径相同，当他们到达终点时，要么相交，要么都为空指针。具体原理如下图所示，本质就是通过延长A和B的路径长度。
var getIntersectionNode = function (headA, headB) {
if (!headA || !headB) return null;
let pA = headA;
let pB = headB;
while (pA != pB) {
// 这里使用 pA ? 而不使用pA.next？ 的原因是，当两个链表不想交时，需要使用 null 节点作为相等判断。如果使用pA.next，则会进入死循环
pA = pA ? pA.next : headB; // 使pA指针走 m + n 长度
pB = pB ? pB.next : headA; // 使pB指针走 m + n 长度
}
return pA;
};
# 反转链表
Q：给出一个单链表的头部节点，然后对其进行反转，返回反转后的链表。
A：假设链表 1 → 2 → 3 → 4 → 5 → null，对其进行遍历，然后逐个反转即可。
// 这里介绍迭代和递归两种解法
var reverseList = function (head) {
/*
解法一，迭代，逐个节点反转
时间复杂度：O(n)
空间复杂度：O(1)
*/
{
if (!head) return null;
let prev = null;
let curr = head;
// 每次遍历，只反转当前节点
while (curr) {
const next = curr.next;
// 反转当前节点
curr.next = prev;
// 记录前驱节点
prev = curr;
// 当前节点后移
curr = next;
}
return prev;
}
/*
解法二，递归，使用递归的特性，由后到前逐个反转。
时间复杂度：O(n)
空间复杂度：O(n)
*/
{
if (!head || !head.next) return head;
// 找到最后一个元素后，层层返回给第一次调用
let newHead = reverseList(head.next);
// head.next 即为当前元素，实现反转
head.next.next = head;
// 实现 原头指针赋空
head.next = null;
return newHead;
}
};
# 附录
写到最后，对于链表一类的问题，看到题目最好用笔画一画，注意细节判断。
这里介绍下其他相关的算法。
# Brent判圈算法
效率比Floyd效率更高