最近在刷 LeetCode 链表专题，这是第二篇，重点拆两个题：合并两个有序链表和链表的中间结点。前者在 LeetCode 是第 21 题，后者是第 876 题，难度都是简单，但如果你用 C 语言刷，会发现它们一点都不“简单”——合并链表要把“归并”思维落到指针上，中间结点要搞清楚快慢指针的循环条件。我见过不少同学把代码背下来，却解释不清为什么偶数个结点时返回的是偏右那个。这篇就按我自己的复盘顺序来写，把原理、代码、坑位一次性讲透。如果你正处在“链表题能看懂答案但自己写不出来”的阶段，这两道题会是非常好的突破口。

1. 合并有序链表和找中间结点，到底考的是同一种能力

很多人把链表题当成“背模板”，今天合并背一段，明天找中点背一段。其实这两道题放在一起刷，比单独刷十道更有效，因为它们背后都指向同一件事：你能不能精确控制指针的移动时机和循环终止条件。

1.1 合并链表：数组归并思想的“去分配化”

合并两个有序链表，本质上就是归并排序里 merge 这一步的链表版本。在数组里做归并，通常需要开一个临时数组，把两个有序子数组的元素从小到大拷贝进去，最后再拷回原数组。链表的最大优势在于：结点都已经存在，你不需要复制任何数据，也不需要申请新的空间，只需要改 next 指针，把两条链的结点按大小顺序重新串起来。

我举个例子。假设两条链分别是 1->3->5 和 2->4->6，合并过程就是不断比较两条链当前的头部：1 比 2 小，把 1 接走，第一条链的指针移到 3；接着 2 比 3 小，把 2 接走，第二条链的指针移到 4；再接着 3 比 4 小……如此反复，直到某条链走完，把剩下那条链的整段直接接上去。整个过程里，结点本身没有移动，变的只是谁指向谁。这就是链表题最核心的思维：操作的是关系，不是数据。

1.2 中间结点：一次遍历里的“差速运动”

找链表中间结点，数组里有下标，直接算 (0 + n) / 2 就能定位。链表没有随机访问，你想知道中间结点在哪，要么先遍历一遍数出长度，再走 n/2 步；要么就用快慢指针。快慢指针的思路可以类比两个人跑步：跑步速度是另一人两倍的人到终点时，速度慢的那位恰好在中点。C 语言里这个思想表达得极其直白：slow = slow->next 是走一步，fast = fast->next->next 是走两步，循环结束的位置就是中间。

这道题真正有意思的地方在于“循环到底什么时候停”。写错的人十有八九不是不懂快慢指针，而是没搞明白 fast 走到哪里才算“到终点”。这个细节单独放到第 3 章细讲，但它已经暴露了链表题的通病：终止条件比循环体本身更容易出错。

1.3 两道题共同的考点：终止条件决定一切

合并链表的核心循环是 while (l1 && l2)，意思是“两边都还有结点才需要比较”；一旦有一边走完，剩下的整段直接拼接。中间结点的核心循环是 while (fast && fast->next)，意思是“快指针还能往前走两步才继续”。这两个条件看似简单，但恰恰是初学者最容易含糊的地方。

我自己刷题有个习惯：拿到链表题先不写代码，先把“初始状态、中间状态、终止状态”三张图在草稿纸上画出来。画到终止状态时你会自然地问自己：此刻指针到底指向谁？哪个指针是 NULL？循环条件该怎么写才能刚好停在这个位置？能把终止状态描述清楚，代码基本就对了七成。这两道题都适合用这个方法练，因为它们的状态变化足够典型，又不至于复杂到画不清楚。

2. 合并两个有序链表：哑结点加尾插法，迭代版最省心

写代码之前，先把要用的操作想明白：每次从两条链里挑较小的头部，接到结果链的末尾。这里的“结果链的末尾”需要一个指针 tail 来记录，问题是结果链的第一个结点从哪来？没有哑结点的时候，第一次插入你要专门判断“tail 是不是空的”，代码立刻多出一个分支。哑结点的作用就是把“第一结点”的特殊情况消掉。

2.1 迭代版核心：栈上哑结点，返回前记得取下 next

我在本地和 LeetCode 上最常用的是这个写法：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode dummy; dummy.next = NULL; struct ListNode* tail = &dummy; while (list1 && list2) { if (list1->val <= list2->val) { tail->next = list1; list1 = list1->next; } else { tail->next = list2; list2 = list2->next; } tail = tail->next; } tail->next = list1 ? list1 : list2; return dummy.next; }

哑结点我推荐声明成局部变量struct ListNode dummy;，而不是用malloc动态分配。理由有两个：第一，哑结点只是一个占位符，不需要真的存在于堆上；第二，动态分配意味着你还要记得free，一旦忘了或者提前 return，就会出现内存泄漏。栈上对象在函数结束自动失效，省心。这里唯一要注意的是返回值必须是dummy.next，因为你不能把哑结点本身交给调用者。

循环体里还有一个容易被忽略的步骤：每次接完一个结点，tail必须往后挪，否则下一次操作会覆盖掉刚接上的 next。我见过有人把tail = tail->next;漏掉，结果跑出来只有两个结点。链表题的调试难点就在这种地方：逻辑上好像每一步都对，但指针位置错了，结果就全偏了。

2.2 递归版：三行代码背后的“信任模型”

迭代版虽然稳，但面试时你最好也掌握递归版，因为代码更短，而且能体现你对递归的理解：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if (!list1) return list2; if (!list2) return list1; if (list1->val <= list2->val) { list1->next = mergeTwoLists(list1->next, list2); return list1; } else { list2->next = mergeTwoLists(list1, list2->next); return list2; } }

递归版的思维模型是：不要想整个过程，只盯住当前这一步。当前比较 list1 和 list2 的头部，谁小谁就是合并后链表的头；选中的那个结点后面应该接什么？交给递归去算。你充分信任mergeTwoLists(list1->next, list2)会返回一个已经合并好的链表，于是只需要把 list1 接到它前面。这就是数学归纳法的代码化。

但这个写法有一个工程上的隐患：递归深度等于链表长度。如果两条链各有一万个结点，最坏情况会压一万层栈，环境稍有约束就可能栈溢出。LeetCode 的测试数据通常不会搞到那种极端程度，所以能过。你心里要清楚这个代价，不能因为代码短就无脑推荐到生产环境。

2.3 边界条件、稳定性和常见翻车点

合并链表的边界条件比较直白：两个链表都为空，返回 NULL；一个是空，返回另一个。迭代版里while (list1 && list2)天然处理了这些情况，最后tail->next = list1 ? list1 : list2;又解决了“某一条先耗尽”的收尾问题。你不需要额外写一堆 if。

比较两个值时，用<=还是<也有一点讲究。用<=意味着当两边相等时，优先取第一个链表的结点，这样合并结果会保持相对顺序，也就是稳定性。如果你将来写链表的归并排序，稳定这个性质是有用的。用<也不会报错，但行为上就不是稳定归并了。

我把实战中容易踩的坑列成了一张表，你可以对照自查：

3. 链表的中间结点：快慢指针的循环条件才是真正的分水岭

合并链表练的是两条链之间的“交替选择”，中间结点练的是同一链上的“差速前进”。这道题我第一次写的时候也能过，但后来发现不同题目对“中间”的定义不一样，循环条件差一点，返回的结点就差一位。这一位在回文链表、重排链表里能把整个结果带偏。

3.1 为什么不用“先数长度再走一半”

先遍历一遍数出 n，再走 n/2 步，这个方案完全正确，时间复杂度和快慢指针一样是 O(n)，空间也是 O(1)。那为什么还要学快慢指针？我认为有三层原因。

第一，快慢指针只需要一趟遍历，如果你面对的是一个流式输入，数据只能从头到尾读一次，两次遍历就不现实了。第二，一趟遍历对 CPU 缓存更友好，因为每个结点只访问一次，而不是从头再走一遍。第三，也是最重要的，快慢指针背后的“差速”思想可以迁移到很多题里，比如判断链表是否有环、找倒数第 k 个结点、找环的入口。你为了一道简单题学会这个模型，后面会省很多力。

3.2 标准循环与变体循环分别返回哪个结点

LeetCode 第 876 题要求偶数个结点时返回偏右的那个中间结点。比如链表是 1->2->3->4，中间结点是 3，不是 2。标准解法是这样：

struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow = head; struct ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; }

用 1->2->3->4 模拟一次：初始 slow 在 1，fast 在 1；第一轮循环后 slow 到 2，fast 到 3；第二轮循环后 slow 到 3，fast 变成 NULL，循环结束，返回 3。4 个结点时返回第 3 个，正好是偏右的中间结点。

但有些题需要的是偏左的那个中间结点。比如回文链表，你要找左半段的末尾，偶数个结点时应该是第 2 个而不是第 3 个，这时循环条件要改成while (fast->next && fast->next->next)：

struct ListNode* middleLeft(struct ListNode* head) { struct ListNode* slow = head; struct ListNode* fast = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } return slow; }

再用 1->2->3->4 模拟：第一轮后 slow 到 2，fast 到 3；第二轮判断时 fast->next 是 4，非空，但 fast->next->next 是 4 的 next，也就是 NULL，条件不满足，循环结束，返回 2。如果是 5 个结点，两种写法返回的都是第 3 个。我把对应关系整理一下：

这个差异不难记，但很容易被忽略。我的建议是：看到“中间结点”先确认题目到底要偏左还是偏右，再看循环条件。LeetCode 的 876 是偏右，写标准循环；回文链表这类题通常需要偏左，就用变体循环。

3.3 快慢指针为什么“先判 fast 再判 fast->next”

C 语言里while (fast && fast->next)的顺序不是随手写的。链表可能为空，也可能只有一个结点。当 fast 是 NULL 时，fast->next就是对空指针解引用，程序直接崩溃。&&运算符有短路求值特性：先算左边，左边为假就根本不会碰右边。所以必须写成fast && fast->next，利用短路保护后续访问。

如果你把条件倒过来写成while (fast->next && fast->next->next)，在空链表上第一轮就会崩。这里没有编译器帮你兜底，因为 C 语言不做运行时的空指针检查。这也是用 C 刷链表题最需要警惕的地方，思路对、代码短，但一个解引用顺序错了就是段错误。

4. C 语言实现里那些不写就体会不到的隐形坑

链表题在 C 语言里的难度很大程度上来自“没有人帮你检查空指针”。Java 或 Python 至少会在运行时报一个相对清晰的异常，C 语言直接就段错误了，而且崩溃位置未必能一眼看出来。这一章只讲我用 C 刷题时经常被卡住的几个细节。

4.1 段错误排查：先怀疑解引用顺序

我遇到过很多次编译通过、逻辑看似没问题，但一运行就崩的情况。链表题的段错误九成来自对 NULL 解引用，剩下的一成是被自己改乱了 next。排查时不要盯着代码反复读，要带着问题找：循环条件里有没有对可能为 NULL 的指针取 next？循环体内取 val 前有没有保证指针非空？

比如合并链表，if (list1->val <= list2->val)这行能安全执行，前提是 while 条件list1 && list2已经成立。你要是把 while 条件写成list1 || list2，就会在某一方为 NULL 时继续进入循环体，然后取 NULL 的 val，结果自然崩溃。这类问题看代码很难看出来，最好的办法是自己在本地用空链表、单结点链表跑一遍。

4.2 哑结点和内存释放：能用栈就别用堆

合并链表里我坚持用栈上哑结点，原因前面说过，避免 malloc/free 的管理负担。但这里有个更隐蔽的坑：如果面试题要求你不能修改原链表，那么合并时必须新建结点，每创建一个结点就malloc一次，返回前要能追踪到所有新结点，最后统一释放。LeetCode 的在线评测不太会强制你做完整释放，但本地跑valgrind或开启地址消毒器时，内存管理就会暴露问题。

如果你只是练习，尽量写成能复用的风格：能修改原链表就修改，不新建结点。这样空间复杂度是 O(1)，也避免“合并完原链表的头找不到了，导致没法释放”的尴尬。

4.3 防御性写法入门的价值

在 LeetCode 的函数签名里，入参要么是合法链表的头指针，要么是 NULL，不会出现“野指针”这种地狱情况。但工程里不同，别人传进来的可能是一个你意想不到的非法状态。我刷题时习惯在函数开头写上：

if (!list1) return list2; if (!list2) return list1;

对于中间结点，也可以加一句：

if (!head) return NULL;

这看起来多余，LeetCode 不加也能过，但我觉得这是培养肌肉记忆的一部分。链表题最大的敌人是空指针，防御性写法的意义不是让代码显得严谨，而是让你养成“碰指针之前先问一句它空不空”的意识。

4.4 本地验证：写一个最小可用的测试脚手架

LeetCode 网页上有测试用例，但只靠它来验证，你练的是“提交答案”，不是“调试能力”。我建议本地写一个小脚手架，自己构造链表、调用函数、打印结果，至少跑几组边界样例再提交。下面的代码足够应付绝大多数链表题：

#include <stdio.h> #include <stdlib.h> struct ListNode { int val; struct ListNode* next; }; struct ListNode* buildList(int* arr, int n) { struct ListNode dummy; dummy.next = NULL; struct ListNode* tail = &dummy; for (int i = 0; i < n; i++) { struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode)); node->val = arr[i]; node->next = NULL; tail->next = node; tail = node; } return dummy.next; } void printList(struct ListNode* head) { while (head) { printf("%d -> ", head->val); head = head->next; } printf("NULL\n"); }

然后你可以在 main 里写：

int a[] = {1, 3, 5}; int b[] = {2, 4, 6}; struct ListNode* la = buildList(a, 3); struct ListNode* lb = buildList(b, 3); struct ListNode* merged = mergeTwoLists(la, lb); printList(merged);

这样跑出来的结果直观多了。本地测试记得覆盖：空链表、单结点、双结点、所有值相同、一条长一条短。把这些样例跑顺了，再提交 LeetCode，基本一次过。

5. 把这两题吃透之后，链表手感是这样练出来的

两道题放在一起刷，真正的收获不是“会做两道题”，而是你开始对指针的移动节奏产生感觉。这种感觉很难用文字描述，但刷多了你会发现自己看链表题的速度明显变快。

5.1 指针移动的两种节奏

合并链表是“二选一前进”：两个指针较劲，谁的值小谁往前走，tail 负责记录已经串好的部分。中间结点是“同向差速”：slow 走一步，fast 走两步，两者共享同一条链，却处于不同位置。这两种节奏基本上覆盖了链表题里最常见的指针关系。

练熟之后，看到“合并两个有序链表”，你会条件反射去想 tail 和哑结点；看到“找中点”，你会条件反射去想 fast 两步、slow 一步。这种条件反射不是靠背题背出来的，是靠画图和模拟演算磨出来的。我每次讲链表题都强调先画三张图，初始、中间、终止，因为指针移动是视觉问题，不是语法问题。

5.2 直接相关的延伸题，按顺序刷会非常顺

这两道题像是两把钥匙，能打开一串后续题目：

我的建议是刷完这两题后，先去做回文链表，因为它会逼你搞清楚“偏左”和“偏右”的差别，也会逼你把反转链表练熟。再去做排序链表，你会发现自己已经在第 2 章和第 3 章把它的两个关键步骤都练过了。

5.3 一点个人刷题心得

用 C 语言刷链表题，最明显的缺点是代码啰嗦、容易崩，但最大的优点是你能真切看见每一步指针的变化。这份“看得见”的感觉，在高级语言里反而没那么强烈。我练这两道题前后写了三遍，第一遍能过但说不清为什么这样写，第二遍开始注意循环条件，第三遍才真正理解偶数结点时为什么返回偏右那个。刷题的价值不在于“AC 了”，而在于你从“会写”到“能讲”之间跨过的距离。如果你现在正卡在链表题，别急着刷数量，挑两三道典型题，把每一步指针变化画明白，收获会比做十道题更大。