企业官网建设流程全解析

链表这个结构，说难不难，说简单也绝对不简单。我刷了几年题，最深的感受是：真正难的树、图、回溯题目，落到最终实现上，都离不开链表那套指针操作；而链表题本身考的不是背代码，是对指针指向和边界条件的掌控力。这次记录的正好是 LeetCode 里两道最经典的链表题——合并两个有序链表、链表的中间结点。一道考你“怎么把两条链串成一条”，一道考你“怎么精准找到中间点”。用 C 语言刷这两题尤其合适，因为它逼着你手动处理指针和内存，哑结点、快慢指针这些套路只要亲身踩过，后面做环形链表、反转链表都会顺很多。这篇文章适合刚起步的刷题新手照着代码敲一遍，也适合想系统整理链表套路的老手一起捋捋思路。

1. 拿到题先想清楚：链表的共性与两题的考察点

1.1 单向链表那些“反直觉”的特质

单向链表最大的特性是“只能单向走”。数组想访问第 k 个元素，直接按下标 O(1) 就完了；链表不行，必须从 head 一路 next 摸过去。也就是说，“定位”这件事在链表里天然是 O(n) 的，所以凡是“第几个”“中间”“倒数第几”这类题目，本质上都在想办法优化这一次遍历，或者把一次遍历玩出花样。

第二个特质是：“改链表”改的不是数据，而是指针。合并链表、反转链表、删除节点，统统不需要你搬动任何节点里的 val，只需要让某些节点的 next 指向新的后继。这一点跟数组的“移动元素”思路完全不同。很多人上来就想着把节点值拷贝到新链表里，思路一开始就跑偏了。

第三个特质是：空指针是最大的敌人。链表题里几乎每一个崩溃都跟 NULL 解引用有关。你访问 cur->next 之前，必须想清楚 cur 是不是已经变成了 NULL；你写 fast = fast->next->next 之前，必须确定 fast 和 fast->next 都不是 NULL。C 语言没有 GC、没有异常保护，踩到空指针就是段错误，所以“用指针前先判空”必须变成肌肉记忆。

还有一个基础但容易忽略的点：链表节点在 C 里是用结构体加自引用指针实现的。

struct ListNode { int val; struct ListNode *next; };

val 存数据，next 存下一个节点的地址。整个链表从头到尾就靠这个 next 串起来，所以链表操作的核心永远只有一句话：把该指的指对，把不该指的断开。

1.2 这两道题正好覆盖链表的两种核心操作

链表的中间结点属于“定位型”题目，你要在一条链上精确找到某个位置；合并两个有序链表属于“重建型”题目，你要在两条链之间重新编排 next 指针。这两种操作基本覆盖了链表题的一大半场景。

把两道题放在一起刷还有个额外好处：中间结点用到的“快慢指针”，本质上是在一次遍历里通过不同步长产生“位置差”；合并链表的迭代则是在两条链表之间交替前进，每一步都要准确更新 tail 指针。你会发现两道题代码都很短，但每一行都在处理“指针该指向哪”的问题。

更重要的是，这两题都不是孤立的。链表的中间结点是回文链表、重排链表的前置步骤，你得先找到中点，才能把后半段单独拎出来反转；合并两个有序链表则是归并排序、合并 K 个有序链表的地基。换句话说，今天花半小时把这两题吃透，后面能省下好几天的功夫。先练“定位”，再练“重建”，两条腿一起走，链表这关才算真正迈过去。

2. 链表的中间结点：从两次遍历到一次遍历的快慢指针

2.1 最直觉的“先数长度再走一半”解法

如果不考虑任何技巧，找中间结点的思路非常直白：先走一遍，数出链表长度 n；然后再从 head 出发，往前走 n/2 步，停下来的位置就是中间结点。

struct ListNode* middleNode(struct ListNode* head) { int n = 0; struct ListNode* cur = head; while (cur != NULL) { n++; cur = cur->next; } cur = head; for (int i = 0; i < n / 2; i++) { cur = cur->next; } return cur; }

这个解法的时间复杂度是 O(n)，但遍历了两次，常数时间比快慢指针大；空间复杂度 O(1)。它的最大优点是极其好懂，面试时可以先说这个思路，再引出优化版，能展现你思考问题的层次感。

注意 n/2 用的是整数除法。n=5 时走 2 步，停在第 3 个节点；n=6 时走 3 步，停在第 4 个节点。题目要求的是“奇数长度返回正中间，偶数长度返回中间偏右的那个”，整数除法 5/2=2、6/2=3 恰好能满足这个语义，不需要单独判断奇偶。这个细节容易被忽略，但实际写起来很顺手。

2.2 快慢指针的实现与最容易写错的循环条件

快慢指针是这类题的标准解：一个慢指针 slow 每次走一步，一个快指针 fast 每次走两步。当 fast 到达链表末尾时，slow 正好停在中间。

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

这段代码最坑的就是 while 条件。很多人图省事只写 fast != NULL，结果在偶数长度的链表上，最后一轮循环结束后 fast 变成 NULL，下一轮循环判断 fast->next 时直接崩溃。还有人只写 fast->next != NULL，但 fast 已经为 NULL 时还在解引用，一样崩。

正确写法是 fast != NULL && fast->next != NULL，两个条件一个都不能少，顺序也不能换。原理是 && 的短路求值：只有 fast 不是 NULL，才有资格去访问 fast->next；然后再保证 fast->next 不是 NULL，才能执行 fast = fast->next->next。C 语言里每次解引用前都要想清楚，这个指针现在有没有可能是 NULL。

提示：如果你遇到的是“返回中间偏左那个节点”变体，把循环条件改成 fast->next != NULL && fast->next->next != NULL 即可。这个变体在回文链表的判断里很常用。

2.3 奇偶长度下的慢指针落点推导

我刚开始学快慢指针时，总觉得慢指针的落点要靠“感觉”，后来认真推了一遍奇偶两种长度，才彻底踏实。

奇数长度例子 [1,2,3,4,5]：

• 初始 slow=1，fast=1
• 第 1 次循环：slow=2，fast=3
• 第 2 次循环：slow=3，fast=5
• fast->next 已经是 NULL，循环结束，slow 停在 3，正是正中间。

偶数长度例子 [1,2,3,4,5,6]：

• 初始 slow=1，fast=1
• 第 1 次循环：slow=2，fast=3
• 第 2 次循环：slow=3，fast=5
• 第 3 次循环：slow=4，fast=NULL
• 循环结束，slow 停在 4，也就是中间偏右的第二个中间结点。

其实不用死记位置：快指针速度是慢指针的两倍，所以 fast 到达终点时，slow 一定走了总路程的一半。fast 每次跨越两个节点，在偶数长度下最终会停在 NULL；而 slow 恰好比“中间偏左”多走半步，于是落在偏右节点上。这个细节正好对上题目的语义。

3. 合并两个有序链表：迭代法的哑结点与指针接力

3.1 哑结点解决了什么问题：头结点不用特判

合并两个有序链表的迭代写法里，哑结点（dummy node）几乎是标配。刚刷题的人会问：我直接在原链表的 head 上操作不行吗？

如果不用哑结点，合并出的新链表头是不确定的：它可能是 l1 的头，也可能是 l2 的头，取决于两个头节点谁更小。于是你得先单独比较一次选出真正的头，再进循环；或者用一个 if 判断当前 tail 是否处于初始状态。无论哪种，都多了一个需要特判的分支，代码立刻变丑。

哑结点的做法是：先在栈上创建一个 dummy 节点，它不存有效数据，只是让“链表的第一个真实节点”也能走统一逻辑。不管两个链表谁小，都是 tail->next = 更小的那个；循环结束后返回 dummy.next，就是真正的新链表头。这个“占位头”的思想，在处理头结点不确定的链表题里极其通用，后面做删除倒数第 N 个节点、合并 K 个有序链表都能用到。

注意，这里 dummy 是栈上的结构体变量，不是 malloc 出来的，所以不需要 free。如果有人写成 struct ListNode* dummy = malloc(sizeof(struct ListNode))，那就必须记得结尾 free，否则内存泄漏。刷题平台通常不检测泄漏，但工程习惯要干净。我推荐栈上版本，少一个隐患。

3.2 完整迭代流程与一组用例的手动推演

迭代合并的代码：

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

这里每一步做的其实是“接力”：tail 永远指向合并结果链表的最后一个节点。每次从 l1 和 l2 的当前头里挑一个更小的，接到 tail 后面；然后让 l1 或 l2 往后挪一位；最后把 tail 也往后挪一位。三件事，顺序一个都不能变。

手动推演一组典型用例，l1 = 1->3->5，l2 = 2->4->6：

1. dummy->NULL，tail 指向 dummy。
2. 1 <= 2，dummy->next = 1，tail 移到 1，l1 移到 3。
3. 3 > 2，1->next = 2，tail 移到 2，l2 移到 4。
4. 3 <= 4，2->next = 3，tail 移到 3，l1 移到 5。
5. 5 > 4，3->next = 4，tail 移到 4，l2 移到 6。
6. 5 <= 6，4->next = 5，tail 移到 5，l1 变为 NULL。
7. 退出 while，tail->next = 6，把 l2 剩余的 6 整个接上。

最终结果 1->2->3->4->5->6。这个推演过程特别重要，我初学链表时总爱快进省略，结果一遇上稍复杂的题目就频频断链。现在每次写之前都在草稿纸上演一遍，tail 指针的更新就是整套逻辑的主心骨。

3.3 O(1)空间的核心原理与新手误区

迭代合并的空间复杂度是 O(1)，因为它没有创建任何新节点，只复用两条链表原有的节点，靠调整 next 指针来重组链表。哑结点在栈上占的只是一小格结构体，跟输入规模无关，不计入额外空间。时间复杂度是 O(m+n)，m 和 n 分别是两条链表的长度，每个节点最多被比较一次。

新手最常见的误区是“为了合并，我新建一条链表放结果”。那种写法每挂一个节点就要 malloc 一次，时间和空间都变成 O(n)，而且 malloc 本身也慢，还要考虑拷贝 val、释放内存，完全是绕远路。链表的天然优势就是改指针就能完成插入、删除、合并，不需要像数组那样搬数据。

还有一个容易忽略的点：整个合并过程没有修改任何节点的 val。如果你看到哪段代码往节点里赋了新值，基本可以断定思路偏了。合并链表跟数据库的“外键指向”有点像，不动记录本身，只动记录之间的关联字段。

4. 合并两个有序链表：递归版三行的简洁与代价

4.1 递归出口与“子问题信任”的代码设计

递归版合并非常短，核心逻辑就三行：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { if (l1 == NULL) return l2; if (l2 == NULL) return l1; if (l1->val <= l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l1, l2->next); return l2; } }

理解递归的关键是“信任子问题”。你要相信调用 mergeTwoLists(l1->next, l2) 会返回一条已经合并好的有序链表，于是只需要把当前的 l1 接到这条链表前面，返回 l1 作为新链表的头。出口则是两个边界：某个链表空了，就直接把另一条链表整个返回，不用再合并。

递归代码虽然短，但我建议读者在刚开始接触时，还是先在纸上把执行流程展开一遍。比如 l1=1->3，l2=2->4，调用链会是：比较 1 和 2，选 1，递归处理 [3] 与 [2->4]；再选 2，递归处理 [3] 与 [4]；再选 3，递归处理 [NULL] 与 [4]；此时 l1 为空，返回 [4]。逐层返回时，链表被依次接回去。展开一次之后，你对递归的“信任”才真正建立，而不是死记代码。

4.2 递归调用的栈开销与O(n)额外空间

递归版的时间复杂度也是 O(n)，每个节点最多被比较一次。但它有一个迭代版没有的成本：每次递归调用都会在调用栈上压入一帧，记录返回地址和局部状态。在最坏情况下，递归深度会达到两个链表的总节点数，额外空间开销从迭代版的 O(1) 变成递归版的 O(n)。

这个 O(n) 在刷题平台上通常不会爆，因为题目给的链表长度一般有限。但到了工程环境，比如要合并两条各有几十万节点的链表，递归深度就可能撑爆默认栈空间，直接段错误。C 语言的默认栈大小在桌面系统上通常是几 MB 到几十 MB，每层递归哪怕只占几十字节，几十万层也扛不住。

还要注意一个细节：这里的递归调用并不是尾递归。尾递归是指递归调用是函数的最后一个操作，编译器可以做优化；而 mergeTwoLists 的递归调用返回后还要执行 return l1，所以每层都必须保留栈帧，基本不可能优化成循环。

4.3 C语言工程视角：什么时候别用递归

写 C 的人对栈要格外敏感。递归在树、分治这类天然有深度上限的场景里很合适，比如平衡二叉树深度是 log 级别；但在链表这种“可以无限延伸”的线性结构上，递归深度完全由数据规模决定，不可控。

还有一个更实际的点：递归版合并会修改原始两条链表的节点指针，但这没问题，因为每个节点只出现在结果链表中一次，不会造成泄漏或重复。真正要避开的是“递归里每次 malloc 新节点”的写法，那样又慢又容易泄漏，最不推荐。

我的建议很明确：面试里可以先讲递归版，体现思路清晰；如果面试官追问能不能优化空间，就把迭代版拿出来。实际工程项目里，我几乎不用递归写链表合并，不是因为它错，而是因为在不确定数据规模的前提下，O(1) 空间的迭代版更稳、可预测性更强。

5. 刷链表题的调试方法与边界用例清单

5.1 画链法：纸上推演比调试器更快的秘诀

链表题调试有个独特的方法：画链法。在纸上画若干个方框代表节点，方框里写 val，旁边留一个箭头代表 next，然后按照代码逻辑一步步修改箭头。

有人觉得这是浪费时间。恰恰相反，对指针操作题来说，手动推演一两遍，往往比在调试器里设断点更高效。链表的“状态”就是那几个指针的指向，一张纸完全装得下；而调试器里每次单步都要看一堆地址，反而不直观。

我自己的流程是：拿到链表题，先不看题解，自己写一版代码；然后挑一个长度 3 到 4 的用例，在纸上把代码跑一遍；如果发现哪一步 next 指向了错误节点，立刻能定位到是哪行代码出了问题。这个方法帮我省了大量调试时间，也让我对“指针修改顺序”特别敏感。比如先接还是先移，差一个顺序就可能丢节点。

5.2 C语言指针操作的三大排查思路

链表题出错，九成以上逃不过这三类：空指针解引用、节点丢失、环或断链。

空指针的排查思路最简单：先看崩溃处访问了几个指针，逐层往前找哪个可能为 NULL。比如 fast->next->next 需要 fast 和 fast->next 都非空，那就在进入这行前打印验证一下。

节点丢失的典型场景是：你让 tail->next = node 之后，忘了更新 tail，下一次又把新节点挂到旧 tail 上，结果后面加的节点全部丢失。排查方法是打印每次挂接后 tail 的 val，如果连续两次出现同一个值，tail 肯定没动。这是合并链表题里最容易踩的坑。

成环和断链是两种极端。断链表现为遍历提前结束，成环则表现为遍历死循环。遇到死循环，不要急着改逻辑，先把指针在纸上画一遍，通常都是某个节点的 next 指回了不该指的节点。比如合并循环里忘了把 l1 或 l2 往后移，下一轮又选中同一个节点，就可能原地打转。

5.3 通用测试用例清单与常见问题速查

链表题只测一个 happy path 远远不够。合并两个有序链表至少应该覆盖：一条链表为空、两条链表长度差异大、有重复值、所有值相等、两链表大小交替穿插。链表的中间结点则必须覆盖奇数和偶数长度，以及只有一个节点的边界情况。

常见问题速查：

这套用例我每次都直接复用。刷题初期整理一次，后面做其他链表题也能当基础模板，省得每次重新想边界。

最后再说一点我个人的体会。链表题是所有数据结构里最适合用“无脑画图验证”来学的题型，因为它的状态变化非常具体，不像动态规划那样抽象。中间结点和合并链表这两题，建议每个人都用迭代和递归各写一遍，再准备一套包含空链表、单节点、奇偶长度的用例反复验证。等这两题吃透了，后面做环形链表、反转链表、回文链表，你会发现核心还是同一套指针控制的逻辑，只是换了个花样而已。