链表题的三种通用解法

2026 大纲 二（三）线性表的应用。结点定义、带头结点约定、插删的通用范式与头插法逆置都在《单链表》，本篇不重复。

三种技巧，都是在绕开同两条限制

链表算法看着花样多，根子上只有两条先天限制在起作用：一是不存表长，位置只能靠走出来；二是只能向后，不能回头。 再加上一条红利：结点可以整个摘走再挂到别处，元素本身不必搬家。 本篇三种技巧，正是这两限一利的直接推论。

结构性问题	它为什么在链表上成立	技巧（及其前提）
不存表长，要定位"与表长成比例的位置"（如中点）	只能走不能算，但两个速度不同的指针能互相当尺子	快慢指针：只扫一遍；速度比 $k : 1$ 定位到 $1 / k$ 处。 $O (n)$ / $O (1)$
不能倒着走，要定位"距表尾 $k$ 个"的位置	把"距尾 $k$ "翻译成"前面那根指针出界"	双指针间距法： $k$ 已知。 $O (n)$ / $O (1)$
两条有序链并成一条，不许开新空间	结点可整个摘走再挂上，元素不必搬动	有序合并：两链各自必须已有序，算法本身不排序。 $O (m + n)$ / $O (1)$

全篇统一约定：代码一律带头结点、 $O (1)$ 辅助空间，两根指针都从 L->next 起算。

先看一眼

加载可视化中...

注意看两根指针之间的间距：它从建立起就再没变过，而"距表尾 $k$ 个"这个本来要倒着数的条件，就这样被翻译成了"前面那根走出表尾"。这一步翻译是双指针法的全部内容。

一、快慢指针

// 求中间结点。约定：n 为偶数时取第 n/2 个，即偏左的那个中点
LNode *middle(LinkList L) {
    if (L->next == NULL) return NULL;              // 空表
    LNode *slow = L->next, *fast = L->next;        // 都从首元结点起
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;                          // 慢 1 步
        fast = fast->next->next;                    // 快 2 步
    }
    return slow;
}

循环不变量：每轮开始时 slow 在第 $t + 1$ 个结点、fast 在第 $2 t + 1$ 个（ $t$ 为轮数）。位置比是由速度比换来的，全程不需要知道 $n$ ——这正是它能绕开"不存表长"这条限制的原因。

这里有个必须先确定的规定：偶数长度时，中点取偏左的还是偏右的？

循环条件	偶数 $n$ 时 `slow` 停在	常用于
`fast->next && fast->next->next`	第 $n / 2$ 个（偏左）	要把表均分成前后两段时——前半正好 $n / 2$ 个
`fast && fast->next`	第 $n / 2 + 1$ 个（偏右）	要让后半段不长于前半段时

🔴 两种都不算错，错的是中途换标准。 分半时用了偏左中点、后续合并却按偏右中点算边界，循环次数就会差一个，尾部结点被漏掉或被处理两次。动笔前先确定要哪一个，全程只用这一个。

还有一层推广值得看清：若 fast 每次走 $k$ 步、slow 走 1 步，那么 fast 到尾时 slow 大约停在全表的 $1 / k$ 处。要取三分点就令 $k = 3$ 。看清这一点，"找中点"就不是一个孤立的招式，而是"用速度比换位置比"这条通法的特例。

不变量的完整论证与逐长度验算（想证一遍或手动模拟时展开）

循环终止的条件是 fast 后面不足两个结点，即 $2 t + 1 \geq n - 1$ ，取最小的 $t$ 得 $t = ⌈ n / 2 ⌉ - 1$ ，于是 slow 停在第 $⌈ n / 2 ⌉$ 个结点。

$n$	循环轮数 $t$	`fast` 终止于	`slow` 终止于	是否偏左中点
1	0	$a_{1}$	$a_{1}$	✓
2	0	$a_{1}$	$a_{1}$	✓（ $n / 2 = 1$ ）
3	1	$a_{3}$	$a_{2}$	✓
4	1	$a_{3}$	$a_{2}$	✓（ $n / 2 = 2$ ）
5	2	$a_{5}$	$a_{3}$	✓
6	2	$a_{5}$	$a_{3}$	✓（ $n / 2 = 3$ ）

循环条件写成 fast != NULL && fast->next != NULL，代码同样"能跑"，但 slow 会多走一步，偶数长度时停在偏右的中点（ $n = 4$ 时停在 $a_{3}$ 而非 $a_{2}$ ）。

同一对快慢指针换一个观察角度，还能解决另一个结构性问题：单链表有没有环。 无环时 fast 必然先走到 NULL；有环时两针最终都会进入环内，此时 fast 相对 slow 每轮靠近 1 步，相对位移每轮减 1，不可能跳过，所以必然追上。⚠️ 但相遇点不是环入口，求入口要再走一趟。

判环的代码，以及求环入口的推导与最小反例（想弄清第二趟为什么必须从首元结点起走就展开）

// 判断带头结点单链表是否有环；有环则返回环内相遇结点，无环返回 NULL
LNode *hasCycle(LinkList L) {
    LNode *slow = L->next, *fast = L->next;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return slow;   // 追上了，说明有环
    }
    return NULL;                          // fast 走到尽头，无环
}

如果还要求出环的入口，有一条能推出来的结论。先先确定原点：slow 与 fast 都是从 首元结点 L->next 出发的，下面所有距离一律以这个出发点为起算点—— 设首元结点到环入口的距离为 $a$ 、入口到相遇点的距离为 $b$ 、环长为 $c$ 。相遇时 slow 走了 $a + b$ 、fast 走了 $a + b + k c$ （ $k \geq 1$ 为 fast 多绕的圈数），由 fast 走的是 slow 的两倍得

2 (a + b) = a + b + k c ⟹ a + b = k c ⟹ a = (k - 1) c + (c - b)

右边的含义是"从相遇点再走 $c - b$ 步到入口，外加绕 $k - 1$ 整圈"。所以让一个指针从首元结点（也就是两针的出发点 L->next）出发、另一个从相遇点出发，同速前进，二者必在环入口相遇。

⚠️ 第二趟的起点必须与 slow/fast 的出发点严格一致。 带头结点时若改从头结点 L 起走，两条路径整体错开一个结点， $a$ 与 $a + 1$ 差的那一步补不回来，两针再也碰不上。拿一个最小的例子验：链为 $L \to a_{1} \to a_{2} \to a_{3} \to a_{4} \to a_{2}$ （入口 $a_{2}$ ，环长 3）。按上面的代码跑，第 3 轮时 slow 与 fast 同时停在 $a_{4}$ ，相遇点即 $a_{4}$ 。此时从 $a_{1}$ 与 $a_{4}$ 同速齐走，一步之后双双到达 $a_{2}$ ，正是入口 ✓；而从 $L$ 与 $a_{4}$ 出发，两针的位置依次是 $(L, a_{4}), (a_{1}, a_{2}), (a_{2}, a_{3}), (a_{3}, a_{4}), (a_{4}, a_{2}), \dots$ 之后按环长循环，永远不相等。

想上机验证判环与找入口：链表判环。

二、双指针间距法

// 查找倒数第 k 个结点（k ≥ 1）：找到输出其 data 返回 1，链长不足 k 返回 0
int findKthFromTail(LinkList L, int k) {
    LNode *fast = L->next, *slow = L->next;   // 都从首元结点起算
    for (int i = 0; i < k; i++) {
        if (fast == NULL) return 0;            // 链长不足 k；这句必须在循环里
        fast = fast->next;                     // fast 先独自走 k 步
    }
    while (fast != NULL) {                     // 两针同速齐走，间距恒为 k
        fast = fast->next;
        slow = slow->next;
    }
    printf("%d", slow->data);
    return 1;
}

循环不变量：第二个循环里恒有"slow 是第 $j$ 个 $\Rightarrow$ fast 是第 $j + k$ 个（或已越过表尾）"；终止时 $j = n - k + 1$ 。也就是说，"距表尾 $k$ "这个向后的条件，被固定间距换成了"fast 出界"这个向前的条件——链表不能回头，就把问题翻译成不用回头的形式。

三处最容易写错的地方：

🔴 先走的步数是 $k$ ，不是 $k - 1$ 。 写成 $k - 1$ 会定位到倒数第 $k + 1$ 个。自检办法是拿 $k = 1$ 代进去：走 1 步后 fast 在 $a_{2}$ ，齐走到 fast 出界时 slow 恰在 $a_{5}$ （最后一个），正确。
带头结点时必须从 L->next 起算。 若两针都从头结点 L 起，整体错位一个结点，结果同样会变成倒数第 $k + 1$ 个。
"链长不足 $k$ "的判断必须放在第一个循环里。 放到循环外再判，fast 已经解引用过 NULL 了。

另一种做法是先遍历一遍数出表长 $n$ ，再从头走 $n - k$ 步。两者时间空间同阶（都是 $O (n)$ / $O (1)$ ），总步数一个 $n + k$ 、一个 $2 n - k$ 。所以双指针的优势只在"单遍扫描"这一条——数据若来自只能读一次的流，两遍法直接不可用，这才是它的真实价值。不要把"更优"理解成"复杂度更低"。

三档边界的逐格验算（想验 k 取 1、等于表长、超过表长三档就展开）

设链长 $n = 5$ ：

$k$	第一循环后 `fast` 在	齐走步数	`slow` 终止于	是否为倒数第 $k$
1	$a_{2}$	4	$a_{5}$	✓
2	$a_{3}$	3	$a_{4}$	✓
5	`NULL`（恰好走完）	0	$a_{1}$	✓（ $k$ 等于表长）
6	第 6 步前已是 `NULL`	—	返回 0	✓（链长不足）

三、有序合并

// 就地合并两个带头结点的递增链表（不新建结点，复用 La 的头结点）
LinkList mergeLists(LinkList La, LinkList Lb) {
    LNode *pa = La->next, *pb = Lb->next;
    LNode *tail = La;                     // 结果链的尾指针，从 La 的头结点起
    while (pa != NULL && pb != NULL) {
        if (pa->data <= pb->data) {       // 相等时取 La 的 → 保持稳定
            tail->next = pa; pa = pa->next;
        } else {
            tail->next = pb; pb = pb->next;
        }
        tail = tail->next;                // 尾指针跟着后移
    }
    tail->next = (pa != NULL) ? pa : pb;  // 剩余段整体挂接，不必逐个搬
    free(Lb);                             // Lb 的头结点已无用
    return La;
}

循环不变量：每轮开始时 tail 指向结果链的最后一个结点，且结果链里每个元素都不大于 pa、pb 所指的值。正因如此，最后一句才能把剩余段整体挂接——再逐个比较是无用功，而且这一句顺带覆盖了"某条链先空"的边界。

🔴 比较写 <= 而不是 <，是为了稳定。 相等时先取 La 的，" $L a$ 中的元素排在 $L b$ 的同值元素之前"这一相对次序才保得住；写成 < 会先取 Lb 的，同值元素的次序被颠倒。

这里有个陷阱：当元素只有关键字、没有附加数据时，两种写法的结果"看起来一样"（都是 $1, 2, 3, 3, 3$ ），所以稳定性问题只在元素带附加信息时才暴露。这与归并排序靠 <= 保稳定是同一件事，判断标准也完全相同。

要求结果递减时不必先合并再逆置：把"挂到 tail 之后"改成"头插到结果链的头结点之后"即可——边摘边头插自动产生逆序，仍然只扫一遍。

时间 $O (m + n)$ （每轮至少让 pa 或 pb 前进一个结点）；比较次数最少 $min (m, n)$ 次（一条链的元素全部小于另一条时，较短的那条走完就退出循环），最多 $m + n - 1$ 次（两条链交替取，最后一个结点不必再比）；空间 $O (1)$ ——只用了三个指针，且不新建任何结点。

稳定性的可验证算例（想看清 <= 改成 < 到底错在哪就展开）

取 $L a = (1_{A}, 3_{A}, 3_{A})$ 、 $L b = (2_{B}, 3_{B})$ ，下标标注元素来自哪条链。

用 <= 合并得 $(1_{A}, 2_{B}, 3_{A}, 3_{A}, 3_{B})$ —— $A$ 的两个 3 仍在 $B$ 的 3 之前 ✓；用 < 则得 $(1_{A}, 2_{B}, 3_{B}, 3_{A}, 3_{A})$ ，次序被换。

四、三种技巧的组合

典型题是链表重排：就地排成 $(a_{1}, a_{n}, a_{2}, a_{n - 1}, \dots)$ 。三类技巧各出一步：

L^{'} = \underset{前半段}{\underset{⏟}{(a_{1}, a_{2}, \dots)}} 与 \underset{后半段逆置}{\underset{⏟}{(a_{n}, a_{n - 1}, \dots)}} 交替

步骤	用到的技巧	结果
① 找中点，从中点后断开	快慢指针（本篇一）	前半段 $(a_{1}, \dots)$ 、后半段 $(\dots, a_{n})$
② 把后半段逆置	头插法逆置	后半段变成 $(a_{n}, a_{n - 1}, \dots)$
③ 两段交替合并	有序合并的变体（本篇三）	目标序列

第 ③ 步是合并的变体：不比较大小，而是轮流各取一个。合并的骨架（维护结果链的尾指针、摘一个挂一个、剩余段整体挂接）原封不动，只把"比大小"换成"轮流"。三步各自 $O (n)$ 时间、 $O (1)$ 空间，串起来仍是 $O (n)$ / $O (1)$ 。

🔴 最容易坏在第 ① 步的断链上。 找到中点 mid 后必须先把后半段的起点 second = mid->next 存下来，再执行 mid->next = NULL；顺序反了就丢掉整个后半段。若干脆忘了断链，前半段仍连着后半段，逆置时会把整条链搅乱，交替合并的结果是一个环。

写完代码，沿 next 从头走一遍，逐条查这三件事——它们覆盖了链表算法几乎全部的错误来源：

查什么	怎么查	典型症状
断链了没有	从头结点出发数结点个数，是否等于预期	中途某个 `next` 被覆盖，后半段丢失。多半是"先覆盖、后读取"的顺序错误
成环了没有	走到某处是否再也遇不到 `NULL`	分段时忘了把前半段的尾置 `NULL`，或交换两段时首尾接反
边界对不对	拿空表、单结点、表长为偶数三个输入手工跑一遍	空表解引用 `NULL`；单结点时 `fast->next->next` 越界；偶数长度时中点的取法不一致

想上机验证：重排链表、合并两个有序链表、合并 K 个有序链表、链表逆置。

考点速记

三条会被反复调用的结论：

三类技巧都在绕开单链表的两条先天限制——不存表长、不能回头。认出限制，技巧就是自然推论。
错误几乎全部出在"指针改动的先后次序"上，只要看一条：即将被覆盖的地址，此刻是否还有别处存着它。
就地操作能做到 $O (1)$ 空间，是因为链表的元素不必搬家——摘一个结点挂到别处，只动指针。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：本篇的技巧主要用在算法设计大题上，而这类题的题面几乎总是同一个模子——"设计一个尽可能高效的算法"，然后要求写设计思想、写代码、说复杂度。见过的几种：

查找倒数第 $k$ 个结点：双指针间距法的原题，一遍扫描 $O (n)$ 、辅助空间 $O (1)$ 。
找两个链表的公共后缀（第一个公共结点）：先各自求长度、让长的那条先走差值步，再同速齐走——仍然是"用固定间距对齐两根指针"这一手。
按元素绝对值去重：借助一个辅助数组标记已出现过的绝对值，一遍扫描摘掉重复结点，本篇的"摘结点"动作原样复用。
就地重排链表：上一节那个三步组合的原题。
两条升序链表合并成一条降序链表：合并 + 头插，一遍扫描，最坏 $O (m + n)$ 。

易错：快指针先走 $k$ 步还是 $k - 1$ 步。 是 $k$ 步。拿 $k = 1$ 代进去一验就知道。

易错：中点的取法中途换了。 分半用偏左、合并按偏右算边界，尾部结点会被漏掉或处理两次。

易错：求环入口时第二趟的起点错了。 必须从两针共同的出发点（带头结点时是 L->next）起走，从头结点 L 起会整体错开一个结点，永不相遇。

易错：分段时忘了断链。 找到中点后要先存后半段起点、再把前半段的尾置 NULL，顺序反了丢半条链，不断链则会得到一个环。

教材出处

两个有序单链表就地归并的算法 MergeList_L（用 LA 的头结点作为结果链的头结点、依次"摘取"两表中值较小的结点插入到结果链最后、 将非空表的剩余段插入到 pc 所指结点之后、最后释放 LB 的头结点），以及比较时用 pa->data <= pb->data 的写法：严蔚敏《数据结构（C 语言版）》（第 2 版），p45，2.7.2 节。
该算法"不需要另建新表的结点空间，而只需将原来两个链表中结点之间的关系解除，重新按元素值非递减的关系将所有结点链接成一个链表即可，所以空间复杂度为 $O (1)$ "：同页。这正是本篇"就地合并"一节的依据。
线性表的应用（线性表的合并、有序表的合并）作为线性表基本操作的组合：同书 p42–p45，2.7 节。

真题练习

2024Q12分 2019Q4113分 2017Q112分 2016Q12分 2015Q4115分 2013Q12分 2012Q4213分 2009Q4215分

链表题的三种通用解法

三种技巧，都是在绕开同两条限制

先看一眼

一、快慢指针

二、双指针间距法

三、有序合并

四、三种技巧的组合

考点速记

相关知识

相关文章

交互体验

真题练习

相关真题（8题）

链表题的三种通用解法 ​

三种技巧，都是在绕开同两条限制 ​

先看一眼 ​

一、快慢指针 ​

二、双指针间距法 ​

三、有序合并 ​

四、三种技巧的组合 ​

考点速记 ​

相关知识 ​

相关文章

交互体验

真题练习 ​

相关真题（8题）

链表题的三种通用解法

三种技巧，都是在绕开同两条限制

先看一眼

一、快慢指针

二、双指针间距法

三、有序合并

四、三种技巧的组合

考点速记

相关知识

真题练习