★ FEATURED ARTICLE 最近在刷 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。比较两个值时用还是也有一点讲究。用意味着当两边相等时优先取第一个链表的结点这样合并结果会保持相对顺序也就是稳定性。如果你将来写链表的归并排序稳定这个性质是有用的。用也不会报错但行为上就不是稳定归并了。我把实战中容易踩的坑列成了一张表你可以对照自查翻车场景错误写法正确表现返回哑结点本身return dummy;或return dummy返回dummy.next循环条件写成“或”while (list1 || list2)用while (list1 list2)否则取 val 时可能访问 NULL忘记移动 tail只做tail-next ...每次还要tail tail-next;不处理空链表直接进入循环比较循环条件本身就覆盖或开头加if (!list1) return list2;相等值时随意用需要稳定时用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 在 1fast 在 1第一轮循环后 slow 到 2fast 到 3第二轮循环后 slow 到 3fast 变成 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 到 2fast 到 3第二轮判断时 fast-next 是 4非空但 fast-next-next 是 4 的 next也就是 NULL条件不满足循环结束返回 2。如果是 5 个结点两种写法返回的都是第 3 个。我把对应关系整理一下链表长度标准循环返回位置变体循环返回位置奇数 2k1第 k1 个第 k1 个偶数 2k第 k1 个偏右第 k 个偏左这个差异不难记但很容易被忽略。我的建议是看到“中间结点”先确认题目到底要偏左还是偏右再看循环条件。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 直接相关的延伸题按顺序刷会非常顺这两道题像是两把钥匙能打开一串后续题目延伸题考点和本文的关系环形链表快慢指针判环快慢指针的经典变体环形链表 II快慢指针求环入口相遇后再从头同步走回文链表找中点 反转后半段正好用“返回偏左中间结点”的变体循环排序链表归并排序 找中点第 2 章和第 3 章的组合题两数相加同时遍历两条链合并链表里“两条链同步走”的节奏感我的建议是刷完这两题后先去做回文链表因为它会逼你搞清楚“偏左”和“偏右”的差别也会逼你把反转链表练熟。再去做排序链表你会发现自己已经在第 2 章和第 3 章把它的两个关键步骤都练过了。5.3 一点个人刷题心得用 C 语言刷链表题最明显的缺点是代码啰嗦、容易崩但最大的优点是你能真切看见每一步指针的变化。这份“看得见”的感觉在高级语言里反而没那么强烈。我练这两道题前后写了三遍第一遍能过但说不清为什么这样写第二遍开始注意循环条件第三遍才真正理解偶数结点时为什么返回偏右那个。刷题的价值不在于“AC 了”而在于你从“会写”到“能讲”之间跨过的距离。如果你现在正卡在链表题别急着刷数量挑两三道典型题把每一步指针变化画明白收获会比做十道题更大。
阅读完成 · 觉得有帮助？
