C# 链表：快慢指针

C# 没有这类题默认的单链表节点类型，LinkedList<T> 也不是。五个模式：一次遍历找中点、Floyd 环检测及其证明、原地反转，以及让特殊情况直接消失的哑节点。

第 1 到第 10 篇讲的是竞赛模式。从这一篇开始，系列转向面试模式。关于链表，第一件要说的事是：你在竞赛里几乎碰不到链表。Codeforces 给你的是数组。面试却总是给你链表。

第二件事是 C# 自己的问题。BCL 里确实有 LinkedList<T>，但它是双向链表，暴露的 LinkedListNode<T> 同时有 Next 和 Previous。这类题说的不是这种结构，用它等于绕开了难点，而不是解决难点。所以这里每个程序都自己声明节点：

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

这是主构造函数，整个类型就这么多。下面每个程序都是完整的，都在 .NET 10 上跑过，输出直接从运行结果粘贴过来。

模式 51 — 一次遍历找中点

最直接的做法是先遍历一遍数出长度，再走一半。两次遍历，而且得知道长度。

换个做法：用两个指针，一个速度是另一个的两倍。快的走到末尾时，慢的正好在中间。

// C# has no singly-linked node type. LinkedList<T> is DOUBLY linked, exposes
// LinkedListNode<T>, and is not what an interview hands you. Declare your own.
static ListNode? Build(params int[] values)
{
    ListNode? head = null;
    for (int i = values.Length - 1; i >= 0; i--) head = new ListNode(values[i], head);
    return head;
}

static string Show(ListNode? n)
{
    var parts = new List<string>();
    for (; n is not null; n = n.Next) parts.Add(n.Value.ToString());
    return string.Join(" -> ", parts);
}

// Two pointers, one moving twice as fast. When fast runs out, slow is halfway.
static ListNode? Middle(ListNode? head, bool secondOfTwo)
{
    ListNode? slow = head, fast = head;
    while (secondOfTwo
        ? fast is not null && fast.Next is not null            // stops later
        : fast?.Next is not null && fast.Next.Next is not null) // stops earlier
    {
        slow = slow!.Next;
        fast = fast!.Next!.Next;
    }
    return slow;
}

foreach (int[] vals in new[] { new[] { 1, 2, 3, 4, 5 }, new[] { 1, 2, 3, 4, 5, 6 } })
{
    var head = Build(vals);
    Console.WriteLine($"{Show(head),-24}  length {vals.Length}");
    Console.WriteLine($"    first of two  -> {Middle(head, false)!.Value}");
    Console.WriteLine($"    second of two -> {Middle(head, true)!.Value}");
}

Console.WriteLine("\nOdd length has one middle and both agree. Even length has two,");
Console.WriteLine("and the loop condition alone decides which one you get.");

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

输出：

1 -> 2 -> 3 -> 4 -> 5     length 5
    first of two  -> 3
    second of two -> 3
1 -> 2 -> 3 -> 4 -> 5 -> 6  length 6
    first of two  -> 3
    second of two -> 4

Odd length has one middle and both agree. Even length has two,
and the loop condition alone decides which one you get.

大家容易搞错的地方是：偶数长度的链表有两个中点，而代码里没有任何地方写明你要哪一个——只有循环条件说了算。while (fast?.Next is not null && fast.Next.Next is not null) 停得早，给你第一个；while (fast is not null && fast.Next is not null) 给你第二个。

先仔细读题，再选条件。别先随手写个条件，然后指望它刚好对。

代价： O(n) 时间，O(1) 空间，一次遍历。

适用场景： 需要找中点，或者要把链表一分为二——链表上的归并排序就从这里开始。

模式 52 — Floyd 环检测

链表会不会绕回自己？用 HashSet<ListNode> 能回答，要 O(n) 内存。用两个指针也能回答，不要额外内存。

// Build a list whose tail loops back to index `enterAt`, or -1 for no cycle.
static ListNode Build(int n, int enterAt)
{
    var nodes = new ListNode[n];
    for (int i = 0; i < n; i++) nodes[i] = new ListNode(i + 1);
    for (int i = 0; i < n - 1; i++) nodes[i].Next = nodes[i + 1];
    if (enterAt >= 0) nodes[n - 1].Next = nodes[enterAt];
    return nodes[0];
}

static bool HasCycle(ListNode head, bool trace)
{
    ListNode? slow = head, fast = head;
    int step = 0;
    while (fast is not null && fast.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
        step++;
        if (trace) Console.WriteLine($"  step {step}: slow at {slow!.Value}, fast at {(fast is null ? "off the end" : fast.Value.ToString())}");
        if (object.ReferenceEquals(slow, fast))
        {
            if (trace) Console.WriteLine($"  they are the same node -> cycle");
            return true;
        }
    }
    if (trace) Console.WriteLine("  fast ran off the end -> no cycle");
    return false;
}

Console.WriteLine("6 nodes, tail links back to index 2 (the node holding 3):");
Console.WriteLine($"  cycle: {HasCycle(Build(6, 2), true)}");

Console.WriteLine("\n6 nodes, no cycle:");
Console.WriteLine($"  cycle: {HasCycle(Build(6, -1), true)}");

Console.WriteLine("\nWhy they must meet: inside the cycle, fast gains exactly one place on slow");
Console.WriteLine("per step. A gap that shrinks by one every step reaches zero. It cannot");
Console.WriteLine("step over slow, because stepping over means the gap went from 1 to -1,");
Console.WriteLine("and it only ever changes by 1.");

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

输出：

6 nodes, tail links back to index 2 (the node holding 3):
  step 1: slow at 2, fast at 3
  step 2: slow at 3, fast at 5
  step 3: slow at 4, fast at 3
  step 4: slow at 5, fast at 5
  they are the same node -> cycle
  cycle: True

6 nodes, no cycle:
  step 1: slow at 2, fast at 3
  step 2: slow at 3, fast at 5
  step 3: slow at 4, fast at off the end
  fast ran off the end -> no cycle
  cycle: False

Why they must meet: inside the cycle, fast gains exactly one place on slow
per step. A gap that shrinks by one every step reaches zero. It cannot
step over slow, because stepping over means the gap went from 1 to -1,
and it only ever changes by 1.

常见的解释是快指针会“套圈”慢指针。这没错，但不算证明：套圈并不显然意味着落在同一个节点上——它也可能一步跨过去。

真正的论证就在输出的最后三行。两个指针都进入环以后，每一步 slow 走一格、fast 走两格，所以两者的差距每步恰好变化一。一个每次只变一、并且朝零逼近的量，一定会正好等于零。它没法从 1 跳到 −1。

还要注意这里用的是 object.ReferenceEquals，而不是 ==。对自定义类来说，== 本来就是引用相等，但显式写出来表明你要的是同一个节点，而不是值相同的节点。一旦有人给类加了 Equals 重写，显式的写法照样正确。

object. 也要写上。单独的 ReferenceEquals 是从 object 继承来的静态方法。在这里这种基于文件的应用里，顶层语句最后会被放进一个生成的类，所以能解析到它。可要是把同样几行粘进 C# scratchpad 或 LINQPad 查询，编译器可能找不到可以继承的地方，你会得到一个“当前上下文中不存在该名称”的错误。加上限定只多七个字符，两边都能用。

代价： O(n) 时间，O(1) 空间。

适用场景： 任何可能出现循环、又负担不起 visited 集合的地方。它不只用于链表：Happy Number 和 Find the Duplicate Number 都是这个模式，只不过“下一个”由函数定义，而不是由指针定义。

模式 53 — 环从哪里开始

检测出环只回答了一半。找环的起点，看起来需要额外记录，其实只要两行。

把一个指针放回表头。两个指针各自一次走一步。它们在入口相遇。

static ListNode Build(int n, int enterAt, out ListNode entry)
{
    var nodes = new ListNode[n];
    for (int i = 0; i < n; i++) nodes[i] = new ListNode(i + 1);
    for (int i = 0; i < n - 1; i++) nodes[i].Next = nodes[i + 1];
    nodes[n - 1].Next = nodes[enterAt];
    entry = nodes[enterAt];
    return nodes[0];
}

int n = 9, enterAt = 3;
ListNode head = Build(n, enterAt, out ListNode realEntry);
int tail = enterAt, cycle = n - enterAt;
Console.WriteLine($"{n} nodes, cycle starts at index {enterAt} (value {realEntry.Value})");
Console.WriteLine($"  L = {tail} nodes before the cycle, C = {cycle} nodes in it\n");

// Phase 1: find any meeting point inside the cycle.
ListNode slow = head, fast = head;
int steps = 0;
do { slow = slow.Next!; fast = fast.Next!.Next!; steps++; }
while (!object.ReferenceEquals(slow, fast));
Console.WriteLine($"phase 1: met at value {slow.Value} after {steps} steps");
Console.WriteLine($"  slow travelled {steps}, fast travelled {steps * 2}");
Console.WriteLine($"  fast went round the cycle {(steps * 2 - steps) / cycle} extra time(s)\n");

// Phase 2: reset one pointer to the head, then advance BOTH one at a time.
ListNode a = head;
int walk = 0;
while (!object.ReferenceEquals(a, slow)) { a = a.Next!; slow = slow.Next!; walk++; }
Console.WriteLine($"phase 2: reset one to head, step both by 1");
Console.WriteLine($"  met again after {walk} steps, at value {a.Value}");
Console.WriteLine($"  correct: {object.ReferenceEquals(a, realEntry)}");

Console.WriteLine($"\nWhy: at the meeting point slow has walked L + k, and fast twice that.");
Console.WriteLine($"So 2(L + k) = L + k + nC, giving L + k = nC, so L = nC - k.");
Console.WriteLine($"Walking L more steps from the meeting point lands exactly on the entry.");
Console.WriteLine($"Here L = {tail} and the phase-2 walk took {walk} steps.");

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

输出：

9 nodes, cycle starts at index 3 (value 4)
  L = 3 nodes before the cycle, C = 6 nodes in it

phase 1: met at value 7 after 6 steps
  slow travelled 6, fast travelled 12
  fast went round the cycle 1 extra time(s)

phase 2: reset one to head, step both by 1
  met again after 3 steps, at value 4
  correct: True

Why: at the meeting point slow has walked L + k, and fast twice that.
So 2(L + k) = L + k + nC, giving L + k = nC, so L = nC - k.
Walking L more steps from the meeting point lands exactly on the entry.
Here L = 3 and the phase-2 walk took 3 steps.

不把算式写出来，这看着就像个技巧。设 L 是环之前的节点数，C 是环的长度。在相遇点，slow 走了 L + k 步（k 是它在环内走的步数），fast 走了两倍。fast 还多绕了 n 圈，所以：

2(L + k) = L + k + nC
    L + k = nC
        L = nC − k

从相遇点再走 L 步，一共走了 k + L = nC 步——正好是整数圈——所以恰好落在入口。上面的运行里 L = 3，第二阶段也正好走了 3 步。

代价： O(n) 时间，O(1) 空间。

适用场景： 题目问环从哪里开始；或者在 1..n 范围内的 n+1 个数里找重复值——那就是把数组当作“下一个”函数的同一个模式。

模式 54 — 原地反转

三个指针，外加一行必须放在最前面的代码。

static ListNode? Build(params int[] v)
{
    ListNode? head = null;
    for (int i = v.Length - 1; i >= 0; i--) head = new ListNode(v[i], head);
    return head;
}
static string Show(ListNode? n)
{
    var p = new List<string>();
    for (; n is not null; n = n.Next) p.Add(n.Value.ToString());
    return string.Join(" -> ", p);
}

// Three pointers. Every step re-points ONE arrow backwards.
static ListNode? Reverse(ListNode? head, bool trace)
{
    ListNode? prev = null, cur = head;
    while (cur is not null)
    {
        ListNode? next = cur.Next;      // save it FIRST — the next line destroys it
        cur.Next = prev;                // flip the arrow
        prev = cur;                     // shuffle both forward
        cur = next;
        if (trace) Console.WriteLine($"    reversed=[{Show(prev)}]   remaining=[{Show(cur)}]");
    }
    return prev;                        // cur is null; prev is the new head
}

Console.WriteLine($"start: {Show(Build(1, 2, 3, 4, 5))}");
Console.WriteLine("reversing:");
var r = Reverse(Build(1, 2, 3, 4, 5), true);
Console.WriteLine($"result: {Show(r)}\n");

// Reverse only positions m..n (1-based). The dummy head removes the special
// case where m == 1 and the list head itself changes.
static ListNode? ReverseBetween(ListNode? head, int m, int n)
{
    var dummy = new ListNode(0, head);
    ListNode before = dummy;
    for (int i = 1; i < m; i++) before = before.Next!;

    ListNode? prev = null, cur = before.Next;
    for (int i = 0; i <= n - m; i++)
    {
        ListNode? next = cur!.Next;
        cur.Next = prev; prev = cur; cur = next;
    }
    before.Next!.Next = cur;    // the old first node is now last in the section
    before.Next = prev;         // and prev is now first
    return dummy.Next;
}

Console.WriteLine($"reverse positions 2..4: {Show(ReverseBetween(Build(1, 2, 3, 4, 5), 2, 4))}");
Console.WriteLine($"reverse positions 1..5: {Show(ReverseBetween(Build(1, 2, 3, 4, 5), 1, 5))}");
Console.WriteLine($"reverse positions 1..1: {Show(ReverseBetween(Build(1, 2, 3, 4, 5), 1, 1))}");

// In groups of k, leaving any short final group alone.
static ListNode? ReverseKGroup(ListNode? head, int k)
{
    ListNode? check = head;
    for (int i = 0; i < k; i++) { if (check is null) return head; check = check.Next; }

    ListNode? prev = null, cur = head;
    for (int i = 0; i < k; i++) { ListNode? nx = cur!.Next; cur.Next = prev; prev = cur; cur = nx; }
    head!.Next = ReverseKGroup(cur, k);   // head is now the tail of this group
    return prev;
}

Console.WriteLine();
foreach (int k in new[] { 2, 3, 5, 6 })
    Console.WriteLine($"k={k}: {Show(ReverseKGroup(Build(1, 2, 3, 4, 5), k))}");

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

输出：

start: 1 -> 2 -> 3 -> 4 -> 5
reversing:
    reversed=[1]   remaining=[2 -> 3 -> 4 -> 5]
    reversed=[2 -> 1]   remaining=[3 -> 4 -> 5]
    reversed=[3 -> 2 -> 1]   remaining=[4 -> 5]
    reversed=[4 -> 3 -> 2 -> 1]   remaining=[5]
    reversed=[5 -> 4 -> 3 -> 2 -> 1]   remaining=[]
result: 5 -> 4 -> 3 -> 2 -> 1

reverse positions 2..4: 1 -> 4 -> 3 -> 2 -> 5
reverse positions 1..5: 5 -> 4 -> 3 -> 2 -> 1
reverse positions 1..1: 1 -> 2 -> 3 -> 4 -> 5

k=2: 2 -> 1 -> 4 -> 3 -> 5
k=3: 3 -> 2 -> 1 -> 4 -> 5
k=5: 5 -> 4 -> 3 -> 2 -> 1
k=6: 1 -> 2 -> 3 -> 4 -> 5

ListNode? next = cur.Next; 必须写在 cur.Next = prev; 之前。后一行会毁掉指向链表剩余部分的唯一指针。把两行调换，既不抛异常也不崩溃——链表只是提前结束了，看起来像是别处某个完全不相干的逻辑错误。

循环结束时，cur 是 null，prev 才是新的头节点。返回 cur 是另一个经典失误。

子链表版本说明了哑节点（dummy head）为什么重要，这正是下一个模式。ReverseBetween(list, 1, 5) 从第一个节点就开始反转，所以链表的头变了——有哑节点在前面，这根本不算特殊情况。另外注意，1..1 正确地什么也没做。

k 个一组的版本对剩余部分递归。反转完一组后，head 成了这一组的尾，下一组正好接在这里。

代价： 迭代版本 O(n) 时间，O(1) 空间。

适用场景： 需要反转链表、部分反转、旋转，或者判断链表是不是回文——最后这个是先用模式 51 找中点，再用这个模式反转后半段。

模式 55 — 哑节点

一个什么都不存的节点，放在真正的链表前面，唯一的目的是让“第一个节点”永远不再是特殊情况。

static ListNode? Build(params int[] v)
{
    ListNode? head = null;
    for (int i = v.Length - 1; i >= 0; i--) head = new ListNode(v[i], head);
    return head;
}
static string Show(ListNode? n)
{
    var p = new List<string>();
    for (; n is not null; n = n.Next) p.Add(n.Value.ToString());
    return p.Count == 0 ? "(empty)" : string.Join(" -> ", p);
}

// WITHOUT a dummy head: the first node is a special case, because there is no
// previous node to attach it to.
static ListNode? MergeAwkward(ListNode? a, ListNode? b)
{
    if (a is null) return b;
    if (b is null) return a;

    ListNode head, tail;
    if (a.Value <= b.Value) { head = tail = a; a = a.Next; }
    else                    { head = tail = b; b = b.Next; }

    while (a is not null && b is not null)
    {
        if (a.Value <= b.Value) { tail.Next = a; a = a.Next; }
        else                    { tail.Next = b; b = b.Next; }
        tail = tail.Next!;
    }
    tail.Next = a ?? b;
    return head;
}

// WITH a dummy head: no special case at all. Every node is attached the same way.
static ListNode? Merge(ListNode? a, ListNode? b)
{
    var dummy = new ListNode(0);
    ListNode tail = dummy;

    while (a is not null && b is not null)
    {
        if (a.Value <= b.Value) { tail.Next = a; a = a.Next; }
        else                    { tail.Next = b; b = b.Next; }
        tail = tail.Next!;
    }
    tail.Next = a ?? b;      // whichever still has nodes; both null is fine too
    return dummy.Next;       // the real head, whatever it turned out to be
}

Console.WriteLine($"a = {Show(Build(1, 3, 5, 7))}");
Console.WriteLine($"b = {Show(Build(2, 3, 6))}");
Console.WriteLine($"merged (dummy head) = {Show(Merge(Build(1, 3, 5, 7), Build(2, 3, 6)))}");
Console.WriteLine($"merged (awkward)    = {Show(MergeAwkward(Build(1, 3, 5, 7), Build(2, 3, 6)))}");
Console.WriteLine();
Console.WriteLine($"empty + [1,2]  = {Show(Merge(null, Build(1, 2)))}");
Console.WriteLine($"empty + empty  = {Show(Merge(null, null))}");
Console.WriteLine();
Console.WriteLine("The dummy version is four lines shorter and has no branch for the");
Console.WriteLine("first node. Both null works too, because dummy.Next was never set.");

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

输出：

a = 1 -> 3 -> 5 -> 7
b = 2 -> 3 -> 6
merged (dummy head) = 1 -> 2 -> 3 -> 3 -> 5 -> 6 -> 7
merged (awkward)    = 1 -> 2 -> 3 -> 3 -> 5 -> 6 -> 7

empty + [1,2]  = 1 -> 2
empty + empty  = (empty)

The dummy version is four lines shorter and has no branch for the
first node. Both null works too, because dummy.Next was never set.

程序里的两个函数输出完全一样。区别在于，别扭的那个版本得先用一个分支定下头节点，循环才能开始，然后又把刚做过的比较重复一遍。哑节点版本用同一种方式接上每个节点，最后返回 dummy.Next——不管它最后是谁。

空链表的情况也顺带处理了。Merge(null, null) 返回 dummy.Next，它从没被赋值过，所以是 null。不需要任何判断。

代价： 多一个节点，函数一返回它就成了垃圾。

适用场景： 链表操作可能改变头节点的时候——合并、删除节点、删除倒数第 n 个节点、按某个值分隔链表。如果你发现自己写了 if (head == null)，后面还跟着一段重复的首轮迭代，这就是信号。

要点

• LinkedList<T> 是双向链表，不是这类题说的链表。 声明一个四行的 ListNode，然后继续。
• 快指针的循环条件决定你拿到哪个中点。 偶数长度的链表有两个中点，代码里别的地方不会告诉你拿的是哪一个。
• Floyd 算法一定终止，证明在于差距每步恰好变化一。 不是“迟早会套圈”——那排除不了一步跨过去的情况。
• L = nC − k 解释了第二阶段为什么落在入口。 把一个指针放回表头，两个都一次走一步。
• 覆盖 cur.Next 之前先保存 next。 顺序写反会悄无声息地截断链表，没有任何异常能帮你定位到那一行。
• 返回 prev，不是 cur。 反转结束时 cur 是 null。
• 哑节点是删掉特殊情况，而不只是把它收拾整齐。 如果你正在为第一个节点单独写一个分支，加个哑节点，把那个分支删掉。

第 12 篇开始讲树：四种遍历顺序，其中那个大家在压力下写不出来的迭代写法，以及层序遍历为什么需要的是队列，而不是小聪明。