链表快慢指针：环检测、倒数节点与链表旋转

摘要

快慢指针（Floyd 判圈算法）是链表题中最具代表性的技巧之一：两个指针以不同速度在链表上移动，通过它们的位置关系来推导链表的结构信息。本篇通过四道经典题：LeetCode 141（环路检测）、LeetCode 142（环路入口）、LeetCode 19（删除倒数第 N 个节点）、LeetCode 61（旋转链表），系统讲解快慢指针的原理、数学推导和应用模式。

第 1 章快慢指针的基本原理

1.1 什么是快慢指针

快慢指针（Fast-Slow Pointer）也叫龟兔赛跑（Floyd’s Cycle Detection Algorithm）：

慢指针（slow）：每次移动 1 步
快指针（fast）：每次移动 2 步

核心直觉：如果链表存在环，快指针一定会”追上”慢指针——就像一个跑道上，快的运动员总会从后面追上慢的运动员（超圈）。

如果链表没有环，快指针会率先到达末尾（fast == null 或 fast.next == null）。

1.2 快慢指针的适用场景

场景	具体应用
检测链表是否有环	LeetCode 141
找环的入口节点	LeetCode 142
找链表中间节点	快指针到末尾时，慢指针在中间
找倒数第 N 个节点	快指针先走 N 步，再同步走
判断链表是否是回文	找中点 + 反转后半段

第 2 章 LeetCode 141：环路检测

2.1 题目

LeetCode 141 - Linked List Cycle（简单）

给你一个链表的头节点 head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。返回 true 或 false。

输入: head = [3,2,0,-4], pos = 1（尾部连接到下标1的节点）
输出: true

输入: head = [1,2], pos = 0
输出: true

输入: head = [1], pos = -1
输出: false

2.2 解法

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;       // 慢指针走 1 步
        fast = fast.next.next;  // 快指针走 2 步
        
        if (slow == fast) {
            return true; // 相遇，说明有环
        }
    }
    
    return false; // fast 到达末尾，无环
}

为什么是 fast != null && fast.next != null？

因为 fast 每次走 2 步，需要保证 fast 本身不为空（才能访问 fast.next），且 fast.next 不为空（才能访问 fast.next.next）。

正确性证明：

设链表无环部分长度为 $a$ ，环的长度为 $c$ 。

当慢指针进入环时，走了 $a$ 步，此时快指针走了 $2 a$ 步，已经在环内的位置是 $(2 a - a) mod c = a mod c$ 处（相对于环入口）。

之后，快指针每次比慢指针多走 1 步，经过最多 $c$ 步，快指针从后面”追上”慢指针（差距从 $c - (a mod c)$ 步减为 0）。所以如果有环，快慢指针必然相遇。

复杂度：时间 $O (n)$ ，空间 $O (1)$ 。

第 3 章 LeetCode 142：环路入口

3.1 题目

LeetCode 142 - Linked List Cycle II（中等）

给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，返回 null。

输入: head = [3,2,0,-4], pos = 1
输出: 节点下标为 1 的节点（值为 2）

3.2 数学推导：找环入口

这道题是 141 的升级版，不只是判断有没有环，还要找到环的入口，需要一点数学推导。

设置变量：

链表头到环入口的距离： $a$
环入口到快慢指针相遇点的距离： $b$
相遇点继续走到环入口的距离： $c$
环长： $b + c$

当快慢指针相遇时：

慢指针走了 $a + b$ 步；快指针走了 $a + b + k (b + c)$ 步（绕环 $k$ 圈后相遇， $k \geq 1$ ）。

由于快指针速度是慢指针的 2 倍：

$2 (a + b) = a + b + k (b + c)$

$a + b = k (b + c)$

$a = k (b + c) - b = (k - 1) (b + c) + c$

关键结论： $a = (k - 1) (b + c) + c$

当 $k = 1$ 时： $a = c$ ！

这意味着：从链表头出发走 $a$ 步，和从相遇点出发走 $a$ 步，会同时到达环入口（因为从相遇点出发 $c$ 步到环入口，再走 $(k - 1)$ 圈环回到入口）。

3.3 代码实现

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    
    // 第一阶段：找相遇点
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break; // 相遇
    }
    
    // 无环（fast 到达末尾，正常退出循环）
    if (fast == null || fast.next == null) return null;
    
    // 第二阶段：找环入口
    // 将 slow 重置到头部，fast 留在相遇点
    // 两者同速前进，相遇处即为环入口
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next; // 注意：这里 fast 走 1 步，不是 2 步
    }
    
    return slow; // slow == fast，即环入口
}

记忆方法

找到相遇点后，把 slow 重置到 head，fast 留在原地，然后两者各走一步直到相遇，相遇处就是环入口。这个技巧来自于数学推导，记住结论比推导过程更重要。

手动验证（[3,2,0,-4]，环入口为节点 2）：

a = 1（头到节点2，走1步）
b = 3（节点2→0→-4→相遇点，假设相遇在-4，走3步... 实际需要算）

让我用具体步骤：
head=3→2→0→-4（-4.next=2，环入口是节点2）

第一阶段：
slow=3, fast=3
step1: slow=2, fast=0
step2: slow=0, fast=2（fast:0→-4→2）
step3: slow=-4, fast=-4（fast:2→0→-4）相遇！

相遇在 -4
a=1（3→2，走1步到环入口）
从相遇点-4走到环入口2: -4→2，走1步，c=1
验证: a=c=1 ✓

第二阶段：
slow 重置到 3，fast 在 -4
step1: slow=2, fast=2 相遇！

返回 slow = 节点2（环入口）✓

复杂度：时间 $O (n)$ ，空间 $O (1)$ 。

第 4 章 LeetCode 19：删除链表的倒数第 N 个节点

4.1 题目

LeetCode 19 - Remove Nth Node From End of List（中等）

给你一个链表，删除链表的倒数第 n 个节点，并且返回链表的头节点。

输入: head = [1,2,3,4,5], n = 2 → 输出: [1,2,3,5]
输入: head = [1], n = 1         → 输出: []
输入: head = [1,2], n = 1       → 输出: [1]

4.2 快慢指针：保持 N 步间距

朴素思路：先遍历一遍链表求长度 $L$ ，目标节点是正数第 $L - n + 1$ 个，再遍历一遍找到它。这需要两遍扫描。

快慢指针（一遍扫描）：

技巧：让快指针比慢指针先走 n+1 步（或 n 步 + 哑节点偏移），之后两指针同步前进。当快指针到达 null 时，慢指针正好在目标节点的前驱节点（prev），可以执行删除。

为什么是 n+1 步？因为我们需要 slow 停在要删除节点的前一个节点，才能执行 slow.next = slow.next.next。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    
    ListNode fast = dummy, slow = dummy;
    
    // fast 先走 n+1 步（+1 是为了让 slow 停在目标前驱）
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }
    
    // fast 和 slow 同步前进，直到 fast 为 null
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // slow 现在在目标节点的前驱，删除目标节点
    slow.next = slow.next.next;
    
    return dummy.next;
}

手动验证（[1,2,3,4,5], n=2，删除倒数第2个即节点4）：

链表: dummy→1→2→3→4→5→null

fast 先走 n+1=3 步:
  dummy→1(1步)→2(2步)→3(3步)
  fast=3, slow=dummy

同步前进:
  fast=4, slow=1
  fast=5, slow=2
  fast=null, slow=3

slow=3 是节点4的前驱，slow.next=slow.next.next
3.next = 5（跳过节点4）

结果: dummy→1→2→3→5 ✓

边界验证（[1,2], n=1，删除最后一个节点）：

fast 先走 2 步: dummy→1→2
fast=2, slow=dummy

同步前进:
  fast=null, slow=1

slow=1 的 slow.next=2，slow.next = null
结果: dummy→1 ✓

边界验证（[1], n=1，删除头节点）：

fast 先走 2 步: dummy→1→null
fast=null, slow=dummy

while(fast!=null) 不执行

slow=dummy，slow.next=1，slow.next = null
结果: dummy→null，返回 dummy.next=null ✓

哑节点的作用在这里体现了出来——删除头节点时与删除其他节点的代码完全一致。

复杂度：时间 $O (n)$ （一遍扫描），空间 $O (1)$ 。

第 5 章 LeetCode 61：旋转链表

5.1 题目

LeetCode 61 - Rotate List（中等）

给你一个链表的头节点 head，旋转链表，将链表每个节点向右移动 k 个位置。

输入: head = [1,2,3,4,5], k = 2 → 输出: [4,5,1,2,3]
输入: head = [0,1,2], k = 4     → 输出: [2,0,1]

5.2 分析：旋转等于”截尾接头”

理解旋转：向右移动 k 位，相当于把链表末尾 k 个节点移到头部。

例如 [1,2,3,4,5], k=2：把后 2 个节点 [4,5] 移到头部，得到 [4,5,1,2,3]。

步骤：

求链表长度 len，同时找到末尾节点
将末尾节点的 next 连接到 head，形成环形链表
计算新头节点的位置：第 len - k%len 个节点（从 1 开始计数）
在新头节点的前驱处断开环

public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null || k == 0) return head;
    
    // 第一步：求链表长度，找末尾节点
    int len = 1;
    ListNode tail = head;
    while (tail.next != null) {
        tail = tail.next;
        len++;
    }
    
    // 第二步：处理 k >= len 的情况（旋转 len 次等于没旋转）
    k = k % len;
    if (k == 0) return head; // 旋转 len 的整数倍，链表不变
    
    // 第三步：形成环
    tail.next = head;
    
    // 第四步：找新头节点的前驱（正数第 len - k 个节点）
    // 走 len - k 步后，指针在新头节点的前驱
    ListNode newTail = head;
    for (int i = 0; i < len - k - 1; i++) {
        newTail = newTail.next;
    }
    
    // 新头节点
    ListNode newHead = newTail.next;
    
    // 第五步：断开环
    newTail.next = null;
    
    return newHead;
}

手动验证（[1,2,3,4,5], k=2）：

len=5, tail=5, k=2%5=2

形成环: 5.next=1 → 1→2→3→4→5→1→...

新头节点是第 5-2=3 个节点（节点4），
新尾节点是第 5-2-1=2 个节点（节点3，即新头的前驱）

newTail 走 len-k-1=2 步:
  初始 newTail=1
  走1步: newTail=2
  走2步: newTail=3

newHead = newTail.next = 4
newTail.next = null（断开3与4之间的连接）

返回 4→5→1→2→3 ✓

手动验证（[0,1,2], k=4）：

len=3, k=4%3=1

形成环: 2.next=0

新头是第 3-1=2 个节点（节点1），新尾是第 1 个节点（节点0）

newTail 走 len-k-1=1 步:
  初始 newTail=0
  走1步: newTail=1

newHead = 1.next = 2
newTail(1).next = null

返回 2→0→1 ✓

复杂度：时间 $O (n)$ （两次线性扫描），空间 $O (1)$ 。

常见错误

忘记处理 k % len == 0 的情况。当 k 是链表长度的整数倍时，链表不变，但代码中已经形成了环，如果不特判直接返回可能导致死循环。

第 6 章快慢指针的模式总结

四道题展示了快慢指针在不同场景下的变形：

题目	快慢指针变体	关键设计
141 环检测	快走2步/慢走1步	有环则必相遇
142 环入口	快走2步/慢走1步找相遇，再同步走1步找入口	相遇后重置一个到头部
19 倒数第N个	快先走N+1步，再同步走1步	维持 N+1 步间距
61 旋转链表	转化为”截尾接头”，不用快慢指针	成环 + 找断点

61 题不是严格的快慢指针

旋转链表虽然也是链表题，但核心技巧是”成环再断”而非快慢指针。之所以放在同篇，是因为它同样考察链表结构理解和边界处理，是链表快慢指针系列后的一道综合练习。

下一篇预告

12 链表反转艺术：局部反转、k 组翻转与节点交换将深入链表反转的三种场景：LeetCode 92（反转 m 到 n 段）、LeetCode 25（每 k 个节点一组翻转）、LeetCode 24（两两交换节点）。反转链表是面试最高频的链表操作，掌握它的迭代和递归两种写法，能应对大部分链表反转变体。

汀的知识碎片

文章导航

11 链表快慢指针：环检测、倒数节点与链表旋转

链表快慢指针：环检测、倒数节点与链表旋转

摘要

第 1 章快慢指针的基本原理

1.1 什么是快慢指针

1.2 快慢指针的适用场景

第 2 章 LeetCode 141：环路检测

2.1 题目

2.2 解法

第 3 章 LeetCode 142：环路入口

3.1 题目

3.2 数学推导：找环入口

3.3 代码实现

第 4 章 LeetCode 19：删除链表的倒数第 N 个节点

4.1 题目

4.2 快慢指针：保持 N 步间距

第 5 章 LeetCode 61：旋转链表

5.1 题目

5.2 分析：旋转等于”截尾接头”

第 6 章快慢指针的模式总结

下一篇预告

On this page

Backlinks

汀的知识碎片

文章导航

11 链表快慢指针：环检测、倒数节点与链表旋转

链表快慢指针：环检测、倒数节点与链表旋转

摘要

第 1 章 快慢指针的基本原理

1.1 什么是快慢指针

1.2 快慢指针的适用场景

第 2 章 LeetCode 141：环路检测

2.1 题目

2.2 解法

第 3 章 LeetCode 142：环路入口

3.1 题目

3.2 数学推导：找环入口

3.3 代码实现

第 4 章 LeetCode 19：删除链表的倒数第 N 个节点

4.1 题目

4.2 快慢指针：保持 N 步间距

第 5 章 LeetCode 61：旋转链表

5.1 题目

5.2 分析：旋转等于”截尾接头”

第 6 章 快慢指针的模式总结

下一篇预告

On this page

Backlinks

第 1 章快慢指针的基本原理

第 6 章快慢指针的模式总结