1. 题目拆解为什么一道基础题能考倒很多人LeetCode第21题“合并两个有序链表”描述极短将两个升序链表合并为一个新的升序链表返回合并后的头节点。示例是1-2-4加上1-3-4得到1-1-2-3-4-4。就这个没了。题目短坑却不少。我面试过不少人也在被面试时写过这道题还帮不少学弟学妹排查过跑不通的代码。它在LeetCode里属于“简单”难度但实际正确率并不高。原因很直接链表题代码量不大却非常吃指针操作的基本功。一个val字段加一个next指针结构简单到不能再简单但越是这种简单结构越容易在细节上翻车——比如头节点丢了、指针死循环、空链表没处理。这篇内容适合三类人看刚开始刷题、想搞懂链表基础操作的新手面试前想快速复习合并类题目的求职者在工作中遇到归并类场景、想了解工程写法的开发者这道题不只是“会写就行”的题目它背后藏着一整套值得掰扯的原则哨兵节点怎么用、引用传递到底怎么影响指针、递归终止条件怎么定、时间和空间复杂度怎么权衡。把这些想明白等于点亮了链表操作的核心技能树。后续再刷反转链表、合并K个有序链表、排序链表这一类题目会顺畅很多。1.1 题目到底在考什么先补一个基础概念链表节点长这样struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };每个节点存两个信息自己的值val和指向下一个节点的指针next。链表和数组最大的区别在于数组是连续内存可以通过下标直接访问链表靠指针串联访问一个节点必须从头开始走。数组“插入”一个元素往往要整体搬移链表插入则只需要调整几个指针指向代价恒定。这道题考的就是你有没有真正理解“调整指针”这件事。所谓合并两个有序链表本质上是一个“归并”过程两个链表各自已经有序你同时从头开始走每次取较小的那个节点接到新链表尾部直到其中一个链表走完然后把剩下的部分整体接上。这个思路和归并排序里的merge步骤完全同源。题目表面问的是“怎么合并”实际考的是三件事会不会用哨兵节点简化边界逻辑能不能正确处理空链表、单链表耗尽这类边界情况有没有想清楚迭代和递归各自的代价很多人的第一版代码大概长这样先判断两个链表哪个头更小把它作为结果头然后挨个比较。这种写法在面试时写出来不算错但代码里会到处是if(l1 l2 ...)这种判断稍不注意就漏掉一种情况。用哨兵节点之后代码会干净非常多。1.2 有序合并的本质归并思想的一次热身把两个有序链表合并这件事抽象来看就一句话维护两个指针指向两条链的当前节点每次选更小的那个输出然后对应指针向后移动。举个例子。l1是1-3-5l2是2-4-6。第一步比较1和21小取1l1移动到3第二步比较3和22小取2l2移动到4第三步比较3和43小取3l1移动到5依此类推最后把剩余的5和6依次接上。最后得到1-2-3-4-5-6。整个过程每走一步至少消耗一个链表的一个节点所以时间复杂度是O(mn)其中m和n是两个链表的长度。空间复杂度取决于写法迭代法是O(1)因为只用了几个指针变量递归法是O(mn)因为递归调用栈会累积到链表长度那么深。这里有个容易误解的点题目说“合并”两个链表结果能不能复用原来的节点可以。这个题默认不去创建新节点而是通过调整原有节点的next指针把两条链“穿”成一条链。很多新手在这里犹豫担心修改指针会影响原链表。其实原链表本身就是输入合并完成后你不再需要原来的两条链直接复用节点是允许的也是所有标准解法的做法。2. 迭代解法一个哨兵节点解决全部边界问题迭代解法是这道题最推荐的写法。它符合直觉、代码短、空间复杂度也是最优的O(1)。核心技巧就一个创建一个哨兵节点dummy node用它作为结果链表的“占位头”最后返回dummy-next。2.1 为什么要引入哨兵节点写链表题最烦的就是头节点的处理。如果不用哨兵你需要先比较l1和l2的头节点把较小者设为结果链表的头然后才能进入循环。这本身不复杂但会引入一次额外的分支判断而且容易和后面的循环逻辑搞混。哨兵节点的思路是先创建一个值无所谓常用0或-1的节点让一个curr指针指向它。然后把两个链表中的节点按顺序接到curr后面最后返回dummy-next。这样一来头节点的选择和中间节点的选择逻辑完全统一不需要任何特判。可以类比一个场景你在排队打菜队伍前面放了一个“虚拟排队队长”所有人都排在队长后面最后你只要看队长后面是谁就知道队伍从哪开始了。哨兵节点在很多链表题里都有奇效比如删除链表倒数第N个节点、两两交换链表中的节点、反转链表II。学会这一招等于拿到一把通用钥匙。2.2 迭代解法代码实现直接看代码语言用Cclass Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* dummy new ListNode(0); ListNode* curr dummy; while (l1 l2) { if (l1-val l2-val) { curr-next l1; l1 l1-next; } else { curr-next l2; l2 l2-next; } curr curr-next; } // 至少有一个链表走完了把剩下那个直接接上 curr-next l1 ? l1 : l2; return dummy-next; } };十行左右结束。说几个关键点。第一while循环条件是l1 l2。这是一个“两个都不为空”的判断。只要其中一个为空循环就停止。这个判断特别容易写错成l1 || l2那样会出现空指针访问因为空节点没有val和next。第二循环内部比较大小用的是而不是。这一步的影响在于当两个节点值相等时优先取l1的节点。虽然本题对相等情况没有特殊要求但保持稳定的选择顺序在面试时是个加分项也方便后续扩展成去重或稳定排序场景。第三循环结束后一定有一个链表还有剩余节点。因为while条件是“两个都不为空”退出循环说明至少有一个是空指针。这时直接把另一个链表的剩余部分整体接上去就行不需要再逐个遍历。有些新手在这里写一个while循环去把剩余节点一个一个接进来功能上没错但没有必要——链表本来就是通过next指针串联的你只需要把curr-next指向那个还没走完的链表头后面一长串就全部带上了。在[l1, l2]均为空的情况下curr-next nullptr也完全没问题。第四返回值是dummy-next而不是dummy本身。新手常见的错误是把dummy返回出去导致结果链表的开头多了一个值为0的节点。dummy只是一个工具人真正的头节点是它后面的那个节点。2.3 迭代解法的执行流程推演拿题目示例走一遍l1是1-2-4l2是1-3-4。创建dummycurr指向dummy。第1轮l1.val1l2.val111成立把l1接到curr-nextl1移向2curr移到l1所在节点。第2轮l1.val2l2.val121不成立把l2接到curr-nextl2移向3curr移到l2节点。第3轮l1.val2l2.val323成立接l1l1移向4curr前进。第4轮l1.val4l2.val3不成立接l2l2移向4curr前进。第5轮l1.val4l2.val444成立接l1l1移向nullcurr前进。第6轮l1已经为空循环退出。curr-next l2l2当前指向原l2的最后一个节点4。注意这里l2指向的节点是4而l2-next本来就是null所以整个链表到这里就结束了。最终dummy-next就是1-1-2-3-4-4和题目示例一致。可以注意到循环总共执行了mn次每次比较耗时O(1)所以总时间复杂度O(mn)。没有使用额外空间除了那个工具人dummy节点所以空间复杂度O(1)。3. 递归解法用函数调用栈“免费”干活递归解法的代码更短面子上更好看但它不是在所有场景都比迭代好。核心要讲清楚递归在这个题目里是怎么运作的以及什么时候该选它。3.1 递归的切入角度迭代解法的思考方式是正着来的我维护两个指针一步步比较、连接。递归解法的思考方式是倒着来的当前两个链表的头节点较小的那个一定是新链表的头节点剩余部分交给函数自己处理。翻译成代码class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; if (l1-val l2-val) { l1-next mergeTwoLists(l1-next, l2); return l1; } else { l2-next mergeTwoLists(l1, l2-next); return l2; } } };这个写法非常优雅。终止条件就是“有一个链表为空返回另一个”递归体就是“挑小的当头递归处理剩下的”。3.2 递归执行过程推演还是用1-2-4和1-3-4来走一遍。调用merge(l11-2-4, l21-3-4)。11所以l1-next merge(2-4, 1-3-4)返回l1。进入merge(2-4, 1-3-4)。21不成立所以l2-next merge(2-4, 3-4)返回l2。进入merge(2-4, 3-4)。23成立所以l1-next merge(4, 3-4)返回l1。进入merge(4, 3-4)。43不成立所以l2-next merge(4, 4)返回l2。进入merge(4, 4)。44成立所以l1-next merge(null, 4)返回l1。进入merge(null, 4)。l1为空直接返回l2也就是4。然后逐层返回。返回的过程中每一层的next指针都已经接好最终形成一个完整的1-1-2-3-4-4链表。细心的读者会发现一个有意思的点递归并不是“回头再处理”而是先一路深入到底再逐层返回返回的时候才把指针组装起来。这正好符合“把问题规模逐步缩小再在小规模上直接得到答案”的递归特性。3.3 递归和迭代怎么选两个解法的时间复杂度相同都是O(mn)。区别在空间复杂度迭代是O(1)递归是O(mn)最坏情况下递归深度等于两个链表的总长度。这意味着合并两个特别长的链表时递归有可能栈溢出。而迭代不会有这个问题。我的建议面试时优先说迭代解法因为空间更优、思路更直接。递归解法可以作为补充展示你理解递归思想。另外如果面试官追问“能不能改成递归”“递归的代价是什么”你能答出空间复杂度差异会明显加分。注意递归解法在l1或l2为空时直接返回另一个链表这个终止条件写起来很简单但千万别漏。漏掉任何一个递归调用就会以空指针访问收场。4. 从刷题到工程合并操作的思维价值题目本身只是22行的算法练习但“合并两个有序序列”的思路在实际工程中出现频率极高。把这一层看透刷题的价值才能发挥出来。4.1 同源变体合并K个有序链表LeetCode第23题“合并K个升序链表”是本题最常见的进阶版给定一个链表数组每个链表都已经升序排列要求将它们合并成一个升序链表。最简单粗暴的做法用一个变量保存当前合并结果逐个调用mergeTwoLists把所有链表串着合并完。这样写代码最少但时间复杂度偏高。假设有K个链表总共有N个节点每轮合并都从头遍历一遍总复杂度会达到O(K*N)。链表多的时候这个代价很可观。更好的做法是用优先队列最小堆。维护一个小顶堆先把所有链表的头节点放进去每次弹出最小值接到结果链后面然后把该节点的next补进去。这样做每次从堆里取最小的复杂度是O(logK)总共N个节点总时间复杂度O(N*logK)空间复杂度O(K)。K个有序链表的合并本质上就是外部排序里“多路归并”的核心逻辑。你理解了LeetCode 21再去理解LeetCode 23的堆做法会发现只是从“两路比较”扩展成了“K路通过堆比较”思路完全一脉相承。4.2 工程里的相似场景链表这个数据结构在真实项目里通常被封装起来了你很少直接操作next指针。但“合并有序数据”这件事到处都在发生有序数组合并。最常见的是双指针归并两个有序数组应用场景包括合并两个有序配置文件、合并两份按时间排序的日志、把两个有序列表合并后取TopK。LeetCode第88题“合并两个有序数组”就是考这个。数据库归并排序。归并排序是稳定的特别适合排序稳定性和大数据量场景。外部排序的核心步骤就是“读若干有序块每块取一个最小值放入堆或比较器选出全局最小输出”。这和合并两个有序链表是同一个思维模型。日志归并。排查多台服务器问题时经常拿到多个按时间排序的日志文件要归并成一条时间线。用归并思路逐条拉取最小时间戳的日志就是工程版的有序链表合并。配置合并。两个配置文件各有有序的key列表要合并成一个有序配置项列表时也是归并逻辑。热词里提到的“maven本地仓库合并”“git分支合并”“pdf合并”虽然是完全不同领域的事情但底层都共享了“把多个有序来源归并成一个”的思想。把“归并”这个meta思想抽出来刷一道题的意义就被放大了。4.3 变体思考逆序合并与去重合并面试时这道题还有两种常见变体提前总结一下有备无患。合并后去重。如果要求合并后的链表中不能出现重复值就需要在合并过程中做一次“值去重”。做法是比较时取较小值如果当前结果链表末尾的值和该节点值相同直接释放或跳过这个节点否则才接入。需要注意的是题目如果要求节点不能复用则要新建节点如果只是考察指针操作复接节点并跳过相同值的即可。合并成降序链表。正序合并之后反转一次就能得到降序。但也有更直接的做法从两个链表的尾部开始向前归并或者用头插法构建降序链表。头插法的思路是每次把较小的节点插到结果链表的头部这样天然就是降序的。这个变体可以帮你更深刻地理解链表节点的插入方式。这些变体题目刷起来并不难但覆盖面广尤其适合在准备面试时集中突破。5. 常见问题与调试实战链表题的bug往往非常隐蔽打印出来可能看不出问题。我把踩过的坑、排查方法和测试用例设计一并总结在这里。5.1 高频错误清单错误一把while(l1 l2)写成while(l1 || l2)。这个错误会导致空指针访问。原因很直白如果l2已经为空但l1不为空循环还会继续进入然后去访问l2-val直接报错。每次写完代码先检查循环条件是不是“两者都要存在”。错误二返回dummy而不是dummy-next。不少人创建了哨兵节点之后返回时手一滑就返回了dummy。结果就是答案一开始多了一个0值节点。我在面试别人时这个错误出现的频率相当高。对策每次用到哨兵节点写return之前自己默念一遍“dummy是工具人工具人不进结果”。错误三在循环里移动了curr但没有重新指向新加入的节点。比如写完curr-next l1之后忘记写curr curr-next。结果是每次循环都把新节点接到同一个节点后面形成“覆盖”甚至“丢失”的效果。这个问题调试的时候特别坑因为链表长度对了但顺序全是错的。错误四把空链表情况单独写一层特判结果特判逻辑还写错了。最保险的办法就是按照标准解法让循环和剩余节点接上逻辑自然处理空链表。不要人为添加不必要的if分支。5.2 链表题的调试利器链表题最怕什么怕“看起来没问题跑起来死循环”。平时写数组题打印printf出来就能看到中间状态。链表不一样你打印一个节点之后还要手动向下走而且一不小心就走到了null程序就崩了。我的办法是写一个辅助打印函数void printList(ListNode* head) { ListNode* cur head; while (cur) { cout cur-val; if (cur-next) cout - ; cur cur-next; } cout endl; }然后在mergeTwoLists的循环里每处理一个节点打印一下当前结果链表。虽然打印不能面面俱到但对发现指针丢失和顺序错位非常有效。另一个技巧是画图。准备一张白纸把两个链表画出来然后手动模拟一遍比较、接指针、移动指针一步一画。这个方法笨但真能帮人理清楚链表操作。我自己在学链表算法时就靠这个方法克服了“总丢头节点”的问题。5.3 测试用例设计清单别只用一个用例跑通就觉得万事大吉。下面这组用例建议全部验证一遍两个空链表预期返回nullptr一个空链表、一个非空链表预期返回非空链表本身一个节点、一个节点例如[1]和[2]预期[1,2]两个链表长度不相等例如[1,2,3]和[4,5]预期[1,2,3,4,5]值全部相等例如[1,1,1]和[1,1,1]预期[1,1,1,1,1,1]一长一短且短的完全嵌在中间例如[1,5,9]和[2,6]预期[1,2,5,6,9]负数和零例如[-3,-1,0]和[-2,2]预期[-3,-2,-1,0,2]这些用例覆盖了空边界、长度差异、重复值和数值符号。刷题时写代码只需要几分钟但设计测试用例往往是区分“会写”和“写对”的分水岭。建议养成习惯每写完一道链表题至少设计5个以上测试用例尤其要包含空值场景。我自己的习惯是先用纸笔把测试用例的预期输出画出来再对着代码手动模拟一遍最后才放到LeetCode上跑。这个流程虽然慢但对理解数据结构本身特别有效。遇到面试时我会先看一下l1和l2是否为空再决定代码的分支——同一道题先处理边界情况会让后续代码简单很多。链表合并这道题真正严谨的准备方式是把“空链表、不等长、值相等”这些容易被忽略的情况都在脑子里过一遍。真正理解了指针的含义任何变体都能应付。工作之后我在代码里几乎没再手写过一个裸链表节点但每次遇到合并有序数据的业务需求脑子里浮现的还是当年这道题的归并框架。这就是基础题的意义所在。