Appearance
链表算法题三板斧
为什么要专门练套路
408 的算法设计大题（41/42 题，13~15 分）特别偏爱单链表：2009 年考倒数第 k 个结点、2012 年考两链表共同后缀、2015 年考按绝对值去重、2019 年考链表重排。这些题面千变万化，但拆开看，反复用的就是三个基本动作：
- 快慢指针——一个走两步一个走一步，找中点
- 双指针定位——一个先走 k 步再同速齐走，找倒数第 k 个
- 尾插合并——两条有序链各出一个比大小，小的接走
外加单链表一文里讲过的头插法逆置，凑齐"四件套"。2019 年那道重排题，就是四件套里的三件直接组合——套路练熟，大题就是搭积木。
408 链表大题默认带头结点（题面会写明），且常要求空间复杂度 O(1)（就地操作，不许开辅助数组）。下面所有代码都按这个口径写。
套路一：快慢指针找中点
slow 每次走 1 步、fast 每次走 2 步，fast 到尾时 slow 正好在中间：
c
// 求带头结点单链表的中间结点（结点数 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;
fast = fast->next->next;
}
return slow;
}手工验证（这是写对快慢指针的唯一办法——画图数步数）：
- n = 5（a₁~a₅）：slow 依次停在 a₁→a₂→a₃，fast 停在 a₁→a₃→a₅ 后循环结束，slow = a₃，正中 ✓
- n = 4（a₁~a₄）：slow 停在 a₂，fast 停在 a₃（
fast->next->next为 NULL）循环结束，slow = a₂ = 第 n/2 个 ✓
易错：循环条件必须是
fast->next && fast->next->next，别写成fast && fast->next——后者会让 slow 多走一步，偶数长度时中点偏右。两种写法都"能跑"，但拆前后两半时半区长度不一样，后续合并的循环边界全得跟着变。做题前先想清楚自己要"偏左中点"还是"偏右中点"，然后从头到尾用同一口径。
套路二：双指针找倒数第 k 个（408·2009/42 原题）
fast 先走 k 步，然后 fast、slow 同速前进；fast 走到表尾后的 NULL 时，slow 与表尾恰好差 k-1 个位置——正是倒数第 k 个：
c
// 408·2009/42：查找带头结点单链表中倒数第 k 个结点（k ≥ 1）
// 查找成功则输出该结点 data 并返回 1，否则只返回 0
// （题面给的指针域名为 link，照题面写）
int findKthFromTail(LinkList list, int k) {
LNode *fast = list->link, *slow = list->link;
for (int i = 0; i < k; i++) {
if (fast == NULL) return 0; // 链长不足 k，查找失败
fast = fast->link; // fast 先走 k 步
}
while (fast != NULL) { // 两针同速齐走
fast = fast->link;
slow = slow->link;
}
printf("%d", slow->data);
return 1;
}正确性一句话：fast 与 slow 始终保持 k 个结点的间距，fast 出界（NULL）时 slow 距表尾正好 k。
- 链长 5、k = 2：fast 先到 a₃；齐走三步后 fast 出界，slow = a₄ = 倒数第 2 ✓
- 链长 5、k = 5：fast 先走 5 步恰好到 NULL，齐走零步，slow = a₁ ✓（边界：k 等于表长）
- 链长 5、k = 6：fast 第 6 步前已经是 NULL，返回 0 ✓
易错：①先走的步数是 k 不是 k-1——k-1 会定位到倒数第 k+1 个；②带头结点的链表要从
list->link（首元结点）起算，从头结点起算整体错位 1；③"先遍历一遍求长度 n、再从头走 n−k 步"的两遍扫描法同样得满分——2009 年评分标准明确方法不限，双指针的优势只是单遍扫描。
把双指针的走位过程做成了动画，可以逐步对照：
写完想验证边界（k=1、k=表长、k 超长）？这道真题在 OJ 可以直接提交跑测：ds-2009-42 倒数第 k 个结点。
套路三：合并两个有序链表
两条递增链表各伸一个指针比大小，小的摘下来尾插到结果链，最后把没走完的剩余段整体接上：
c
// 就地合并两个带头结点的递增链表 La、Lb（不新建结点，复用 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->next = pa ? pa : pb一句完成，逐结点搬运是无谓功 <=取等号：相等时先取 La 的结点，归并才稳定——和归并排序<=保稳定是同一个道理
想上机验证：OJ 上有对应训练题 p2310 合并两个有序链表，进阶版 p2311 合并 K 个有序链表。
组合拳：2019 年真题 = 三招连招
408·2019/41：带头结点单链表 L = (a₁, a₂, …, aₙ)，设计空间复杂度 O(1) 的算法，重排为 L' = (a₁, aₙ, a₂, aₙ₋₁, …)。
看着唬人，拆开就是本文套路的流水线：
- 快慢指针找中点（套路一）——把链表分成前半和后半两段
- 后半段头插法逆置（单链表一文的套路）——(aₙ, aₙ₋₁, …)
- 两段交替合并（套路三的变体，不比大小、轮流各取一个）——得到目标序列
每一步都是 O(n) 时间、O(1) 空间，总体达标。这道题的完整代码、评分点和逐步图解在题库里：ds-2019-41 链表重排，写完可以在 OJ 提交验证：p2313 重排链表。
易错：分两半时前半的尾结点要断链（
mid->next = NULL之前先保存后半起点），否则逆置后半时前半还连着，交替合并会成环。链表大题写完务必沿 next 走一遍查"断链了没、成环了没"。
答题心法（大题通用）
- 先写设计思想再写代码：评分标准里"设计思想"单独占分（2019 年占 3 分），思路对、代码有小瑕疵仍能拿大部分分
- 先画图再动笔：每一步指针变化在草稿纸上画出来，指针操作顺序错误（先断后接）是链表题的第一大死因
- 报清复杂度：题面有"尽可能高效"字样时，时间/空间复杂度是采分点，漏写白丢分
- 方法不必最优也要正确：两遍扫描、开计数数组等"笨办法"通常能拿正确性分，想不出最优解先把正确解写满
考研高频考点
- 双指针找倒数第 k 个结点（2009/42 原题，先走 k 步的边界处理）
- 快慢指针找中点（循环条件与奇偶长度讨论）
- 两个有序链表合并（递增尾插 / 递减头插，剩余段挂接）
- 套路组合型大题（2019/41：找中点 + 逆置 + 交替合并）
- 链表就地操作的空间复杂度分析（O(1) 约束下不许开辅助数组）
- 断链与成环检查（重排类题目的隐藏扣分点）