4.4　快慢指针与经典应用

学习目标：学完本节，你能

• 用快慢指针判断链表是否有环，并说清为什么两个指针一定会相遇；
• 推导并实现"找环入口"的算法；
• 用快慢指针找中点、找倒数第 $k$ 个节点；
• 说清快慢指针相对哈希表的优势到底在哪。

先修：4.1–4.3。 固定术语：快慢指针、判圈。 环境与版本：.NET 8 / C# 12。 预计阅读：30 分钟。

一、直觉：操场上的两个人

想象一个环形跑道上，两个人同时从起点出发：

• 慢的人速度是 1 米/秒
• 快的人速度是 2 米/秒

他们会相遇吗？

会。而且一定会 —— 因为跑道是环形的，快的人迟早会从后面追上慢的人（"套圈"）。

如果跑道不是环形的呢？ 那快的人会先跑到终点，然后就结束了 —— 永远不会相遇。

这就是判环的全部原理： 两个速度不同的指针在链表中前进，如果链表有环，它们一定会在环内相遇；如果没有环，快指针会先撞到 null 而结束。

这个算法有个正式名字叫 Floyd 判圈算法（Floyd's Cycle Detection），也叫"龟兔赛跑算法"。

二、四个应用的总览

快慢指针在链表问题里有四个高频应用，全部只用 $O(1)$ 额外空间：

共同点：都是利用"两个指针的相对位置关系"，不依赖任何额外存储。

三、完整代码

新建控制台项目，粘贴以下代码：

using System.Diagnostics;

// ==================== 快慢指针的四个经典应用 ====================

// ---------- 应用 1：判断链表有没有环 ----------
static bool HasCycle(Node head)
{
    Node? slow = head, fast = head;
    while (fast != null && fast.Next != null)
    {
        slow = slow!.Next;              // 慢指针每次走 1 步
        fast = fast.Next.Next;          // 快指针每次走 2 步
        if (ReferenceEquals(slow, fast)) return true;   // 追上了，说明有环
    }
    return false;
}

// 对照组：用哈希表记录访问过的节点，需要 O(n) 额外空间
static bool HasCycleWithSet(Node head)
{
    var seen = new HashSet<Node>(ReferenceEqualityComparer.Instance);
    for (Node? p = head; p != null; p = p.Next)
        if (!seen.Add(p)) return true;
    return false;
}

// ---------- 应用 2：找环的入口 ----------
static Node? FindCycleStart(Node head)
{
    Node? slow = head, fast = head;

    // 第一阶段：先让两个指针相遇
    while (fast != null && fast.Next != null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
        if (ReferenceEquals(slow, fast)) break;
    }

    if (fast == null || fast.Next == null) return null;   // 没有环

    // 第二阶段：一个从头出发，一个从相遇点出发，同速前进 —— 相遇处就是环的入口
    Node? p1 = head, p2 = slow;
    while (!ReferenceEquals(p1, p2))
    {
        p1 = p1!.Next;
        p2 = p2!.Next;
    }
    return p1;
}

// ---------- 应用 3：找中点 ----------
static Node? FindMiddle(Node head)
{
    Node? slow = head, fast = head;
    while (fast?.Next != null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
    }
    return slow;                        // 快指针走到底时，慢指针正好在中点
}

// ---------- 应用 4：找倒数第 k 个节点 ----------
static Node? FindKthFromEnd(Node head, int k)
{
    if (k <= 0) return null;

    Node? fast = head;
    for (int i = 0; i < k; i++)         // 先让快指针先走 k 步
    {
        if (fast == null) return null;  // k 比链表还长
        fast = fast.Next;
    }

    Node? slow = head;
    while (fast != null)                // 然后一起走，快指针到尾时慢指针正好在倒数第 k 个
    {
        slow = slow!.Next;
        fast = fast.Next;
    }
    return slow;
}

// ---------- 工具：构造 1..n 的链表，返回头节点 ----------
static Node BuildList(int n)
{
    Node head = new(1);
    Node cur = head;
    for (int i = 2; i <= n; i++)
    {
        cur.Next = new Node(i);
        cur = cur.Next;
    }
    return head;
}

// ==================== 主流程 ====================

Console.WriteLine("=== 应用 1 & 2：判环与找环入口 ===");
Console.WriteLine();

// 构造 1 -> 2 -> 3 -> 4 -> 5 -> 6，然后让 6 指回 3
Node head6 = new(1);
{
    Node cur = head6;
    for (int i = 2; i <= 6; i++) { cur.Next = new Node(i); cur = cur.Next; }
    Node entry = head6.Next!.Next!;     // 节点 3
    cur.Next = entry;                   // 尾节点指回 3，形成环
}

Console.WriteLine("  链表: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> (回到 3)");
Console.WriteLine($"  HasCycle 判定    = {HasCycle(head6)}");
Node? entryFound = FindCycleStart(head6);
Console.WriteLine($"  环的入口节点值   = {entryFound?.Value}   (预期 3)");
Console.WriteLine($"  入口节点引用正确 = {ReferenceEquals(entryFound, head6.Next!.Next)}");
Console.WriteLine();

// 无环链表做对照
Node acyclic = new(1);
{
    Node cur = acyclic;
    for (int i = 2; i <= 6; i++) { cur.Next = new Node(i); cur = cur.Next; }
}
Console.WriteLine("  对照：无环链表 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null");
Console.WriteLine($"  HasCycle 判定    = {HasCycle(acyclic)}");
Console.WriteLine($"  环的入口         = {FindCycleStart(acyclic)?.Value.ToString() ?? "null（没有环）"}");
Console.WriteLine();

Console.WriteLine("=== 应用 3：找中点 ===");
Console.WriteLine();

foreach (int n in new[] { 1, 2, 3, 4, 5, 6 })
{
    Node h = new(1);
    Node c = h;
    for (int i = 2; i <= n; i++) { c.Next = new Node(i); c = c.Next; }

    Node? mid = FindMiddle(h);
    Console.Write($"  {n} 个节点 [1..{n}] 的中点 = {mid!.Value}");
    Console.WriteLine(n % 2 == 1 ? "   (奇数个：正中间那个)" : "   (偶数个：靠后的那个)");
}
Console.WriteLine();

Console.WriteLine("=== 应用 4：找倒数第 k 个节点 ===");
Console.WriteLine();

Node h10 = new(1);
{
    Node c = h10;
    for (int i = 2; i <= 10; i++) { c.Next = new Node(i); c = c.Next; }
}
Console.WriteLine("  链表: 1 -> 2 -> ... -> 10");
foreach (int k in new[] { 1, 3, 5, 10 })
{
    Node? r = FindKthFromEnd(h10, k);
    Console.WriteLine($"    倒数第 {k,2} 个 = {r?.Value}");
}
Console.WriteLine($"    倒数第 11 个 = {FindKthFromEnd(h10, 11)?.Value.ToString() ?? "null（k 超过链表长度）"}");
Console.WriteLine();

// ==================== 性能与空间对比 ====================

Console.WriteLine("=== 判环的两种做法：时间与空间 ===");
Console.WriteLine();

const int N = 1_000_000;
Node bigHead = BuildList(N);

var sw = Stopwatch.StartNew();

// 用「累计分配字节数」而不是 GC.GetTotalMemory：
// 后者测的是「当前占用」，而哈希表在方法返回后就被回收了，根本测不到。
long alloc0 = GC.GetAllocatedBytesForCurrentThread();
bool r1 = HasCycle(bigHead);
long alloc1 = GC.GetAllocatedBytesForCurrentThread();
sw.Stop();
double fastSlowMs = sw.Elapsed.TotalMilliseconds;

sw.Restart();
bool r2 = HasCycleWithSet(bigHead);
long alloc2 = GC.GetAllocatedBytesForCurrentThread();
sw.Stop();
double setMs = sw.Elapsed.TotalMilliseconds;

double fastSlowKb = (alloc1 - alloc0) / 1024.0;
double setKb = (alloc2 - alloc1) / 1024.0;

Console.WriteLine($"  链表长度 {N:N0}，无环（最坏情况：两种方法都必须走完全程）");
Console.WriteLine();
Console.WriteLine($"  快慢指针: 结果={r1,-5} | {fastSlowMs,8:F2} ms | 新分配内存 {fastSlowKb,9:F1} KB");
Console.WriteLine($"  哈希表  : 结果={r2,-5} | {setMs,8:F2} ms | 新分配内存 {setKb,9:F1} KB");
Console.WriteLine();
Console.WriteLine($"  快慢指针一点额外内存都没分配（{fastSlowKb:F1} KB），哈希表分配了 {setKb / 1024:F1} MB。");
Console.WriteLine();

// ==================== 节点定义 ====================

public class Node
{
    public int Value;
    public Node? Next;
    public Node(int value) => Value = value;
}

实测输出（.NET 8 Release）：

=== 应用 1 & 2：判环与找环入口 ===

  链表: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> (回到 3)
  HasCycle 判定    = True
  环的入口节点值   = 3   (预期 3)
  入口节点引用正确 = True

  对照：无环链表 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
  HasCycle 判定    = False
  环的入口         = null（没有环）

=== 应用 3：找中点 ===

  1 个节点 [1..1] 的中点 = 1   (奇数个：正中间那个)
  2 个节点 [1..2] 的中点 = 2   (偶数个：靠后的那个)
  3 个节点 [1..3] 的中点 = 2   (奇数个：正中间那个)
  4 个节点 [1..4] 的中点 = 3   (偶数个：靠后的那个)
  5 个节点 [1..5] 的中点 = 3   (奇数个：正中间那个)
  6 个节点 [1..6] 的中点 = 4   (偶数个：靠后的那个)

=== 应用 4：找倒数第 k 个节点 ===

  链表: 1 -> 2 -> ... -> 10
    倒数第  1 个 = 10
    倒数第  3 个 = 8
    倒数第  5 个 = 6
    倒数第 10 个 = 1
    倒数第 11 个 = null（k 超过链表长度）

=== 判环的两种做法：时间与空间 ===

  链表长度 1,000,000，无环（最坏情况：两种方法都必须走完全程）

  快慢指针: 结果=False |     1.58 ms | 新分配内存       0.0 KB
  哈希表  : 结果=False |    84.03 ms | 新分配内存   52625.6 KB

  快慢指针一点额外内存都没分配（0.0 KB），哈希表分配了 51.4 MB。

四、为什么两个指针一定会相遇？

这是快慢指针唯一需要证明的地方。很多人会答"因为快的一定会追上慢的"，但这只是在重复结论。真正的理由是：

在环内，快指针相对于慢指针的速度是恒定的 1 步/轮。

拆开来看：

1. 在进入环之前，两个指针都在直线上，快指针走在前面。如果链表没有环，快指针会先撞到 null，算法结束。
2. 一旦两个指针都进入环，它们就永远出不去了。此时：
   • 慢指针每轮走 1 步
   • 快指针每轮走 2 步
   • 所以每过一轮，快指针相对于慢指针就前进 1 步
3. 设环长为 $L$。两个指针在环上的距离（从快指针到慢指针的"前方距离"）是 $d$，其中 $0 \le d < L$。
   • 每轮这个距离减少 1
   • 所以最多 $L$ 轮之后，$d$ 必然变成 0 —— 相遇

关键点：相对速度是 1，而 1 和 $L$ 一定互质（任何数和 1 都互质），所以不会"跳过"慢指针。

如果速度差不是 1 呢？ 比如快指针走 3 步、慢指针走 1 步，相对速度是 2。此时如果环长 $L$ 是偶数，快指针就可能一直跳过慢指针，永不相遇。

所以"快指针走 2 步"不是随便选的 —— 它保证了相对速度为 1，从而保证一定相遇。（这一点很多讲快慢指针的文章都没说清楚。）

五、找环入口：一个漂亮的推导

判环只回答了"有没有环"。但很多时候我们想知道环从哪里开始 —— 比如检测一个链式结构的循环引用，你需要找到那个"绕回来"的位置。

算法分两个阶段：

1. 第一阶段：按上面的方法走，直到两个指针相遇。
2. 第二阶段：让一个指针回到头节点，另一个留在相遇点，然后两个指针以相同的速度（每次 1 步）前进。它们再次相遇的位置，就是环的入口。

为什么？来推导一下。

设：

• $a$ = 从头节点到环入口的距离
• $b$ = 从环入口到相遇点的距离
• $L$ = 环的长度

head ──a──> 入口 ──b──> 相遇点
              ↑            │
              └──── 环 ────┘
                 (环长 L)

相遇时两个指针各走了多远？

• 慢指针：走了 $a + b$（进环后只走了 $b$，还没绕完一圈）

  为什么慢指针一定没绕完一圈？因为快指针每轮只比它多走 1 步，所以快指针进环时，慢指针最多在环内走了不到半圈 —— 相遇一定发生在慢指针跑完第一圈之前。

• 快指针：走了 $a + b + nL$（多绕了 $n$ 圈，$n \ge 1$）

快指针走的路程是慢指针的 2 倍：

$$2(a + b) = a + b + nL$$

化简：

$$a + b = nL \quad \Longrightarrow \quad \boxed{a = nL - b}$$

这意味着什么？

从相遇点出发，再走 $a$ 步会到哪里？相遇点在环内、距离入口 $b$ 的位置。从相遇点往前走：

$$b + a = b + (nL - b) = nL$$

正好是环长的整数倍 —— 也就是说，回到了环的入口！

所以：

• 一个指针从头节点走 $a$ 步 → 到达环入口
• 另一个指针从相遇点走 $a$ 步 → 也到达环入口

两个指针以相同速度前进，走同样的 $a$ 步，所以它们一定在环入口相遇。

这个推导的美妙之处在于：我们根本不知道 $a$、$b$、$L$ 具体是多少，但等式 $a = nL - b$ 告诉我们"从头走 $a$ 步"和"从相遇点走 $a$ 步"是等价的目的地。

这就是为什么第二阶段不需要任何额外信息，只要两个同速指针就够了。

实测验证（链表 1→2→3→4→5→6，6 指回 3）：

  环的入口节点值   = 3   (预期 3)
  入口节点引用正确 = True

六、找中点：注意"中点"的定义

Node? slow = head, fast = head;
while (fast?.Next != null)
{
    slow = slow!.Next;
    fast = fast.Next.Next;
}
return slow;

实测结果：

偶数个节点时，"中点"有两个，这个实现返回的是靠后的那一个。

如果你需要靠前的那个（比如归并排序里要把链表切成两半，切在靠前的位置能避免某一边为空），把循环条件改成：

while (fast.Next != null && fast.Next.Next != null)

这个细节很容易被忽略，但在实际使用中是会出错的。 比如"把链表分成两半"时，如果取靠后的中点，长度为 2 的链表会被切成 1 和 1；如果取靠前的中点，会切成 1 和 1（一样）—— 但长度为 1 时，取靠前的写法会返回 head 本身，而靠后的写法……需要具体分析。

写链表题时，"偶数长度怎么办"永远值得多想一秒。

七、找倒数第 $k$ 个：保持固定的距离

Node? fast = head;
for (int i = 0; i < k; i++)         // 快指针先走 k 步
{
    if (fast == null) return null;  // k 超过链表长度
    fast = fast.Next;
}

Node? slow = head;
while (fast != null)                // 然后同速前进
{
    slow = slow!.Next;
    fast = fast.Next;
}
return slow;

原理：让快指针先走 $k$ 步，这样两个指针之间就始终隔着 $k$ 个节点。当快指针走到 null（链表末尾）时，慢指针正好在倒数第 $k$ 个位置。

初始:   slow→1  2  3  4  5  6  7  8  9  10  fast(走了3步，在4)
前进:   slow→1  2  3  4  5  6  7  8  9  10  fast
        ...
结束:   1  2  3  4  5  6  7  slow→8  9  10  fast→null
                                 ↑
                            倒数第 3 个 = 8 ✓

实测：倒数第 1 个 = 10，倒数第 3 个 = 8，倒数第 5 个 = 6，倒数第 10 个 = 1，倒数第 11 个 = null（越界返回 null 而不是崩溃）。

注意边界处理：k 比链表长度还大时，第一个循环里的 if (fast == null) return null; 会提前退出，不会抛空引用异常。这是这类"先走几步"的算法最容易漏掉的地方。

经典变体：如果要求删除倒数第 $k$ 个节点，需要拿到它的前驱。这时用一个哨兵节点（4.3 节）就能优雅地解决 —— 因为哨兵保证了头节点也有前驱。

八、为什么要用快慢指针？——空间的账

  快慢指针: 结果=False |     1.58 ms | 新分配内存       0.0 KB
  哈希表  : 结果=False |    84.03 ms | 新分配内存   52625.6 KB

判环最简单的做法其实是：遍历一遍，把每个访问过的节点存进 HashSet；如果遇到已经在集合里的节点，就说明有环。

这两种做法的对比：

时间上快慢指针还快 53 倍 —— 因为哈希表每个节点都要算哈希、分配内存、处理冲突。

但真正的重点是那 0 KB。

在内存受限的场景里，"$O(n)$ 额外空间"可能是不可接受的：

• 嵌入式设备：可能只有几百 KB 的可用内存
• 高并发服务：1000 个并发请求 × 51 MB = 51 GB，直接打爆
• 实时系统：哈希表的内存分配会触发 GC，造成不可预测的停顿

快慢指针一个字节都不用，这是它无可替代的价值。

九、练习

练习 4.4.1（判断） 判断对错并说明理由： (a) 快慢指针一定能判断出链表是否有环。 (b) 快指针每次走 3 步、慢指针走 1 步，也能保证相遇。 (c) 快慢指针判环的时间复杂度是 $O(n)$。

练习 4.4.2（推演） 链表为 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8，其中 8.Next 指向 4。 请手工推演快慢指针的相遇过程：列出每一轮之后两个指针分别在哪个节点，并指出它们在哪相遇。 然后验证：$a$（头到入口）、$b$（入口到相遇点）、$L$（环长）分别是多少，$a = nL - b$ 是否成立。

练习 4.4.3（写代码） 给定一个链表的头节点，判断它是否回文（正着读和反着读一样）。 要求：$O(n)$ 时间、$O(1)$ 额外空间。 （提示：用快慢指针找中点 + 反转后半部分。）

练习 4.4.4（变体） 用快慢指针找出一个有序链表中的重复元素并删除，使每个值只出现一次。要求 $O(n)$ 时间、$O(1)$ 空间。

练习 4.4.5（挑战·重新排序） 给定链表 L0 → L1 → ... → Ln-1 → Ln，把它重新排列成 L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ... 要求：$O(n)$ 时间、$O(1)$ 额外空间。 （提示：这道题需要三个技巧的组合。）

十、练习答案

4.4.1

• (a) 对。 只要链表确实有环，快慢指针（速度差为 1）一定会相遇。如果没环，快指针会先撞到 null。

  前提是速度差为 1（见 (b)）。

• (b) 错。 快指针走 3 步、慢指针走 1 步，相对速度是 2。如果环长 $L$ 是偶数，快指针会一直跳过慢指针，永远不会相遇。

  具体例子：环长 $L = 4$，快慢指针初始在环上的距离差为 1（快指针落后慢指针 1 步，或者等价地说快指针在前方 3 步）。

  每轮相对前进 2 步。距离序列是 $3 \to 1 \to 3 \to 1 \to \cdots$（模 4），永远到不了 0。

  所以"相对速度必须与环长互质"。相对速度为 1 时，1 与任何 $L$ 互质，一定相遇。相对速度为 2 时，只在 $L$ 为奇数时保证相遇。

• (c) 对。 慢指针最多走 $n$ 步，快指针最多走 $2n$ 步，总操作是 $O(n)$。

  更精确地说：在无环的情况下，快指针走到 null 就结束，耗时 $n/2$ 轮。在有环的情况下，最多再走 $L$ 轮就会相遇（$L \le n$）。所以总的上界是 $O(n)$。

4.4.2

链表：1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → (回到 4)

环是 4 → 5 → 6 → 7 → 8 → 4，所以 $L = 5$，入口是节点 4。

从头节点 1 到入口 4 的距离：1 → 2 → 3 → 4，走了 3 条边，所以 $a = 3$。

推演（每一轮：slow 走 1 步，fast 走 2 步）：

在节点 6 相遇。

验证：从入口 4 到相遇点 6 的距离是 4 → 5 → 6，走了 2 条边，所以 $b = 2$。

检查等式 $a = nL - b$：

$$nL - b = n \times 5 - 2$$

取 $n = 1$：$5 - 2 = 3 = a$ ✓ 成立！

再用第二阶段验证：一个指针从头节点 1 出发，另一个从相遇点 6 出发，同速前进：

两个指针在节点 4 相遇 —— 正是环的入口 ✓

这个练习值得亲手推一遍。 它会让你对"$a = nL - b$"这个式子有直觉，而不是只记住结论。

4.4.3

static bool IsPalindrome(Node head)
{
    if (head?.Next == null) return true;      // 空表或单节点，都是回文

    // 第 1 步：快慢指针找中点（这里要「靠前」的中点，方便切分）
    Node slow = head, fast = head;
    while (fast.Next != null && fast.Next.Next != null)
    {
        slow = slow.Next!;
        fast = fast.Next.Next;
    }
    // 此时 slow 是前半部分的最后一个节点

    // 第 2 步：反转后半部分
    Node? prev = null;
    Node? cur = slow.Next;
    while (cur != null)
    {
        Node? next = cur.Next;
        cur.Next = prev;
        prev = cur;
        cur = next;
    }
    // 现在 prev 是反转后的后半部分的头

    // 第 3 步：从两端向中间比较
    Node? p1 = head, p2 = prev;
    bool result = true;
    while (p2 != null)
    {
        if (p1!.Value != p2.Value) { result = false; break; }
        p1 = p1.Next;
        p2 = p2.Next;
    }

    // 第 4 步（可选）：把后半部分反转回去，恢复原链表
    // 工程上做这一步是好习惯 —— 不要「偷偷」修改调用者的数据结构
    cur = prev;
    prev = null;
    while (cur != null)
    {
        Node? next = cur.Next;
        cur.Next = prev;
        prev = cur;
        cur = next;
    }
    slow.Next = prev;

    return result;
}

三个要点：

1. 找中点时要"靠前"的中点（用 fast.Next != null && fast.Next.Next != null）。这样 slow.Next 开始的后半部分长度不会超过前半部分，切分更均匀。
2. 比较时以 p2（较短的那半）为准。奇数长度时前半部分会多一个元素（正中间那个），它不需要参与比较。
3. 最后把链表恢复原状。这是一个很容易被忽略的工程习惯：你只是在"判断"，不应该留下副作用。

4.4.4

static Node? RemoveDuplicates(Node head)
{
    if (head == null) return null;

    Node cur = head;
    while (cur.Next != null)
    {
        if (cur.Value == cur.Next.Value)
            cur.Next = cur.Next.Next;      // 跳过重复的节点
        else
            cur = cur.Next;                // 只在「不重复」时才前进
    }
    return head;
}

关键点：比较的是 cur 和 cur.Next，而不是两个同时前进的指针。

因为链表是有序的，重复元素一定相邻。所以只需要一次遍历，遇到相同的就跳过。

注意 else 的位置：只有确认不重复时才 cur = cur.Next。如果写成每次都前进，就会漏掉"连续三个相同值"的情况（比如 1,1,1）。

这和 3.3 节"同向双指针"的原地去重是同一个思想，只不过在数组上要用 slow/fast 两个下标，在链表上只需要一个 cur —— 因为链表的"跳过"就是改指针，不需要移动数据。

4.4.5

这道题需要三个技巧组合：

static void ReorderList(Node head)
{
    if (head?.Next == null) return;

    // ---------- 第 1 步：快慢指针找中点 ----------
    Node slow = head, fast = head;
    while (fast.Next != null && fast.Next.Next != null)
    {
        slow = slow.Next!;
        fast = fast.Next.Next;
    }

    // ---------- 第 2 步：反转后半部分 ----------
    Node? prev = null;
    Node? cur = slow.Next;
    slow.Next = null;                        // 从中间断开，变成两条独立的链
    while (cur != null)
    {
        Node? next = cur.Next;
        cur.Next = prev;
        prev = cur;
        cur = next;
    }
    // prev 是反转后后半部分的头

    // ---------- 第 3 步：交替合并两条链 ----------
    Node? first = head;
    Node? second = prev;
    while (second != null)
    {
        Node? firstNext = first!.Next;
        Node? secondNext = second.Next;

        first.Next = second;                 // L0 -> Ln
        if (firstNext == null) break;
        second.Next = firstNext;             // Ln -> L1

        first = firstNext;
        second = secondNext;
    }
}

推演（1 → 2 → 3 → 4 → 5）：

验证：L0=1, L4=5, L1=2, L3=4, L2=3 → 1 → 5 → 2 → 4 → 3 ✓

三个技巧分别是：

1. 快慢指针找中点 —— 把链表切成两半
2. 反转链表 —— 让后半部分可以"从后往前"取
3. 交替合并 —— 把两条链编织在一起

这道题的价值在于：它把三个独立的链表技巧组合起来，而且全部是 $O(1)$ 空间。

面对复杂链表题的一般方法：先问"我需要什么能力"（找到中点？反转？合并？），再看"哪个已知技巧能提供这个能力"，最后组合。链表题的难度往往来自组合，而不是单个技巧本身。

十一、常见错误

十二、本节总结

1. 快慢指针（Floyd 判圈算法）用两个速度不同的指针解决问题，额外空间 $O(1)$。
2. 判环原理：有环时快指针一定会"套圈"追上慢指针；无环时快指针会先撞到 null。
3. 为什么一定相遇：快慢指针的相对速度是 1，而 1 与任何环长互质，所以不会跳过。速度差不是 1 时可能永远追不上。
4. 找环入口：相遇后，一个指针回头节点、一个留在相遇点，同速前进，相遇处即入口。依据是推导出的 $a = nL - b$。
5. 找中点：偶数个节点时有两个中点，你的实现返回哪个取决于循环条件 —— 写之前先确认需求。
6. 找倒数第 $k$ 个：快指针先走 $k$ 步，保持固定间距。注意 $k$ 过大时的越界处理。
7. 实测对比：100 万节点的判环，快慢指针 1.58 ms / 0 KB，哈希表 84.03 ms / 51.4 MB。快慢指针在时间和空间上都完胜。

本章小结：第 4 章把链表讲透了。

• 4.1 揭示了链表的本质：引用赋值不搬数据 —— 这是 $O(1)$ 增删的根源，也是它内存开销 8 倍、遍历慢 3.8～7.4 倍的原因。
• 4.2 讲清了三种形态的取舍，特别是双向链表用 8 字节/节点换来了"删除已知节点 $O(1)$"。
• 4.3 给出了工程上真正重要的东西：哨兵节点消除边界特判，以及"状态没更新干净"这类隐蔽 bug 的测试方法。
• 4.4 展示了链表最优雅的部分：两个指针就能解决判环、找入口、找中点、找倒数第 k 个，且不用一字节额外空间。

但也要记住本章反复出现的那条结论：链表不是"更好的数组"，它是一个在特定场景下才有优势的结构。微软官方建议优先用 List<T>，这个建议是有道理的。

下一章衔接：链表解决了"中间插入要挪动元素"的问题，但它引入了新的问题 —— 它不支持"按位置快速访问"。有没有一种结构，既能 $O(1)$ 插入，又能 $O(1)$ 查找？

有。它叫哈希表，是 C# 里 Dictionary<TKey, TValue> 的底层结构，也是你每天都在用、却未必真正理解的东西。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "4.4",
  "title": "快慢指针与经典应用",
  "covered": [
    "Floyd 判圈算法的原理与操场类比",
    "四个应用（判环/找入口/找中点/找倒数第k个）的统一视角",
    "「相对速度必须为 1」的相遇保证与反例",
    "找环入口的完整数学推导（a = nL - b）",
    "偶数长度时中点的两种定义与循环条件的关系",
    "实测：快慢指针 1.58ms/0KB vs 哈希表 84.03ms/51.4MB",
    "回文链表的 O(1) 空间解法与副作用消除",
    "重排链表的三技巧组合（找中点+反转+交替合并）",
    "手工推演 a=3, b=2, L=5 的完整验证"
  ],
  "unresolved": [
    "哨兵节点删除倒数第 k 个的完整实现已在 4.3 铺垫",
    "归并排序对链表的应用留到 8.1",
    "哈希表判重的工程替代方案留到第 6 章"
  ],
  "canonical_terms": {
    "快慢指针": "两个速度不同的指针同向遍历，利用相对位置关系求解",
    "判圈": "判断链表等链式结构中是否存在环"
  },
  "symbols_units": {
    "a": "头节点到环入口的距离",
    "b": "环入口到相遇点的距离",
    "L": "环的长度",
    "n": "快指针比慢指针多绕的圈数"
  },
  "assumptions": [
    "读者已掌握 4.1-4.3 的链表基础、三种形态与哨兵节点",
    "读者理解 C# 的引用相等（ReferenceEquals）与对象相等（Equals）的区别"
  ],
  "word_count_actual": 3080,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch04/Sec44/",
    "实测数据逐项核对：入口节点3、中点序列1/2/2/3/3/4、倒数第k个、1.58ms vs 84.03ms",
    "练习 4.4.2 的推演结果（a=3,b=2,L=5,n=1）已手工验算并与代码输出一致",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "内存测量初版用 GC.GetTotalMemory 无法测到已回收的哈希表；已改用 GC.GetAllocatedBytesForCurrentThread 统计累计分配量"
  ],
  "next": "5.1 栈：后进先出"
}