如果你面试前只打算认真看一道链表题那大概率就是“合并两个有序链表”。这个题目的描述很简短给定两个已经按升序排列的单链表把它们合并成一个新的升序单链表并返回。它看起来简单却是我从面试官视角最爱用的题目之一因为短短十几行代码里能同时看出一个人对指针操作、边界条件、递归思维和复杂度分析的熟悉程度。不管你是准备校招、社招还是在日常开发里想补一补数据结构底子这道题都值得从头到尾手写一遍。很多人刷题时习惯直接看答案看过就以为自己会了结果到了白板面试环节一个 dummy 节点都说不清。这里不会只贴一份可运行代码而是想把你最需要理解的几个点拆开讲清楚为什么“有序”是突破口、为什么要用哨兵节点、递归终止条件怎么设计、空链表怎么处理以及合并 K 个链表时怎么复用这里的思路。代码示例会同时给 Java、Python 和 C 语言版本三种语言各有各的脾性但核心逻辑完全一致。无论你主力语言是哪一种建议至少把迭代法和递归法各默写一遍。1. 先把题目拆明白合并两个有序链表到底在考什么1.1 题目描述与选项误区两个输入链表都是非递减有序的这一句话里藏着很多信息。首先链表可以为空空链表不是非法输入而是一种正常边界。其次非递减意味着相等的节点可以连续出现排序结果允许重复值。很多人第一次做这道题第一反应是把两个链表的所有节点值取出来放进数组再统一排序最后重建链表。这个思路能跑通但完全没利用题目给的条件时间复杂度至少是 O((nm)log(nm))空间复杂度也高面试官看到这种答案大概率会追问一句“能不能不用排序”。第二个常见误区是把合并和拼接混为一谈。直接l1尾.next l2是不行的因为 l2 内部虽然有序但 l1 的所有元素未必都比 l2 的第一个元素小。只有逐节点比较并穿插才能保证全局有序。第三个误区是觉得链表操作可以用数组替代甚至想先把链表转成字符串再处理。链表不是数组它没有随机访问能力也不应该为了合并而改变最本质的链式结构。正确的做法是在原节点基础上调整 next 指针在 O(1) 额外空间内完成归并而不是创造一批临时对象再复制一遍。1.2 “有序”二字为什么是破题关键因为有序所以你可以做线性归并不需要回头访问任何节点。类比一个场景手上有两副已经按点数排好的扑克牌现在要合成一副新牌你会把两副牌最上面一张都比较一下拿走较小的那张然后继续比较各自新的最上面一张。整个过程不会回头去翻已经拿走的牌因为你已经通过“有序”确认过当前这轮拿出的牌一定比后续所有待处理牌都小。把这个类比翻译成链表操作就是两个指针 l1 和 l2 分别指向两个链表的当前头节点。每次比较 l1.val 和 l2.val取较小的节点接到结果链表尾部并把对应链表的指针后移一位。由于两个链表自身有序后继节点一定不小于当前节点所以这种贪心选择是全局正确的。最终某一方先走到头另一方剩下的节点天然有序直接整体接上即可。有序性把“排序”降维成了“归并”时间复杂度也被压到线性的 O(nm)。这也是合并操作能成为归并排序、外部排序、多路数据流合并等算法基石的原因。1.3 链表遍历与指针移动的基本功写合并之前先确认链表遍历你真的熟。经典遍历模板是while (cur ! null) { ... cur cur.next; }。不熟的人写合并时常出两个问题一是 while 条件写成了while (cur.next ! null)导致最后一个节点没被处理二是移动指针时顺序错了比如先改了tail.next再把l1后移结果把 l1 的后续链表整个弄丢。链表节点之间的关系只靠 next 维系丢失一个指针就可能让一大段节点变成不可达对象。我建议你先写一个辅助函数遍历两个链表并打印每个节点值。能顺利输出再开始写合并。这一步看似基础却能避免所有因指针移动顺序导致的连环 bug。链表题里最常见的翻车现场就是“我以为断的是这条链结果断的是另一条”所以任何涉及xx.next yy的代码都要在心里问一句原来xx.next指向谁现在它被改掉了有没有别的地方还依赖这个旧引用2. 写代码前必须想清楚的三个细节节点、哨兵和递归出口2.1 链表节点的几种定义写法先统一节点结构。C 语言里最常见的就是struct ListNodeJava 里是ListNode类Python 则用class Node。语言不同核心字段却一模一样一个保存值的val一个保存下一个节点引用的next。下面给出三种常见写法方便你直接对照。public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } }class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextstruct ListNode { int val; struct ListNode *next; };很多语言标准库里的链表节点还会带prev指针形成双向链表但合并有序双链表的逻辑与单链表几乎没有差别只是额外多维护一条prev链路。刷题时先以单链表为准理解 next 的指向变化就够了。工程上如果自己封装链表记得把构造函数也写完整否则每次创建节点都要手动赋值很容易漏字段。2.2 哨兵节点避免头指针判空地狱这是我强调最多的一点。合并过程中你根本不知道结果链表的头节点最终来自 l1 还是 l2因为两个链表元素大小是交错的。如果不用哨兵节点每次添加节点前都要判断result null代码会多出一堆分支而且边界条件特别容易写错。哨兵节点是一个值无关紧要的占位节点通常叫dummy它的 next 最终指向结果链表的真实头节点。用代码讲就是ListNode dummy new ListNode(-1); ListNode tail dummy;之后所有新节点都接在tail.next上并且tail不断后移。循环结束后返回dummy.next。这样做有两个直接好处第一不需要单独处理“结果链表最初为空”的情况因为dummy本身让尾部一直有一个可挂接的锚点第二循环结束时无论哪条链表先耗尽你都能直接拿到结果起点。这个技巧不是这道题独有链表的删除、反转、两两交换等题目里都一样好用可以说是链表操作的万能起手式。2.3 递归解法的终止条件设计递归写法的核心是把大问题缩小成“一个节点加一个小问题”合并 l1 和 l2等价于比较两个头节点取较小者 x然后让x.next merge(x所在链表的剩余部分, 另一条链表)。这个思路很优雅但递归必须有明确的终止条件。合并两个有序链表只有两个终止条件l1 为空返回 l2l2 为空返回 l1。很多人写递归时只记得主逻辑忘记在函数入口判断空链表结果要么空指针要么栈溢出。终止条件的顺序也有讲究。先判断 l1 是否为空再判断 l2 是否为空两者都为空时前一个判断已经会返回 l2此时 l2 也是 null所以不需要额外写第三个 if。如果你把“两者都为空”单独抽出来逻辑上没错但代码冗余。递归在这里虽然代码短但要注意它会有 nm 层递归调用。链表特别长时比如几万个节点递归很可能栈溢出。C 语言默认栈空间有限嵌入式开发里栈空间更紧张所以递归写法更多是展示思维工程落地优先迭代。2.4 迭代与递归怎么选这道题两种写法面试时都要会。如果候选人只写了递归我会追问迭代写法只写了迭代我会追问递归写法。原因很简单递归展示的是把大问题拆成小问题的能力迭代展示的是对指针和内存的掌控力。实际工程里我更倾向于迭代理由有三个。第一递归调用栈深度等于链表长度长度为几万时可能爆栈第二递归会原地修改传入节点的 next调用方可能不希望原链表被改变第三迭代代码虽然没有递归优雅但控制流更直白更容易做断点调试。不过递归版本确实很精练也只有短短几行作为思路验证和单元测试对照非常有价值。如果你在写递归时觉得大脑过载可以先写迭代再把迭代里“更新 tail 并移动指针”的部分替换成“递归调用并返回头节点”转换起来会顺很多。3. 迭代法与递归法逐行实现附完整代码和复杂度分析3.1 迭代法从头到尾谁小接谁迭代法完整代码如下以 Java 为例public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(-1); ListNode tail dummy; 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; }逐行拆开看。dummy的值随便填常用 -1 或 0因为最终会跳过这个节点。tail永远指向结果链表的最后一个节点初始时指向dummy。while条件是“两个链表都还没走完”只要有一个走完循环就结束。比较时取较小节点接到tail.next然后只移动对应链表的指针。为什么只动一边因为较小节点被取走后它的链表需要补充下一个候选节点而另一边的头节点依然留在原位参与下一轮比较。每一步比较后tail都要前进一位否则后续节点会全部覆盖到同一个 next 上。循环结束后最多只剩一条链表还有剩余。剩余链表本身已经有序并且它的当前头节点一定大于结果链表当前的尾节点所以直接把tail.next指向剩余链表的头节点即可不需要再逐节点复制。最后返回dummy.next跳过哨兵节点得到真正的结果头节点。很多人写完后会忘记tail tail.next或者返回时写成了return dummy这两种错误几乎占了链表题提交失败的一半。Python 版本逻辑完全一样只是语法上更简洁def merge_two_lists(l1: ListNode, l2: ListNode) - ListNode: dummy ListNode() tail dummy while l1 and l2: if l1.val l2.val: tail.next l1 l1 l1.next else: tail.next l2 l2 l2.next tail tail.next tail.next l1 or l2 return dummy.nexttail.next l1 or l2是处理剩余节点的简写如果 l1 非空就接 l1否则接 l2。如果你担心可读性写成显式条件也一样。Python 里注意节点对象默认不是空值所以条件判断直接写while l1 and l2即可不需要写l1 is not None。3.2 递归法把“合并”拆成“一个节点再合并”递归法完整代码如下public ListNode mergeTwoLists(ListNode l1, 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; } }入口必须先判断空链表这既是终止条件也是处理边界输入的唯一出口。接着比较头节点值。如果 l1 较小那么 l1 一定是合并结果的头节点它的 next 应该等于“l1.next 与完整 l2 合并”的结果反之 l2 较小就把 l2 作为头节点递归合并 l1 与 l2.next。这样每层递归只确定一个头节点下一层处理剩余链表直到某一条链表为空。递归写法最大的坑是“修改了原节点”。l1.next mergeTwoLists(l1.next, l2)这行代码会直接改写 l1 原始链表里的 next 指针。如果调用方后续还要用原链表做别的事结果就会出问题。你在面试时最好主动问一句“题目允不允许改变原链表结构”如果允许递归没问题如果不允许就需要复制节点或者改用“先遍历到数组再重建链表”的方案。递归的时间复杂度也是 O(nm)但空间复杂度是 O(nm)因为递归调用栈要保存每一层状态。3.3 时间复杂度与空间复杂度怎么算迭代法每一轮循环比较并移动一个节点最多处理 nm 个节点时间复杂度 O(nm)。过程中只用了 dummy 和 tail 两个额外指针空间复杂度 O(1)这是最优的原地操作不依赖链表长度。递归法时间复杂度同样 O(nm)因为每个节点最多被比较一次但空间复杂度不是 O(1)而是 O(nm)它来自递归调用栈。面试时说出这个差异很加分能说明你不是只会背代码。这里再补充一个容易被忽略的细节无论迭代还是递归最坏情况都是两个链表长度接近且元素交替大小比如 l1 [1,3,5]l2 [2,4,6]这样每一轮都要比较共执行 nm-1 次比较。如果其中一个链表非常短比如 l2 只有 1 个节点循环会提前结束剩余部分整体挂接实际比较次数接近 n 次远小于 nm。但这个差异不影响大 O 复杂度评估只影响常数因子。4. 边界条件与调试实录空链表、相等值和指针断链4.1 空链表与单节点链表边界条件能不能考虑全是这道题拉开差距的关键。先说最常见的两个输入都可能为 null。这时候迭代法 while 循环直接不进tail.next (l1 ! null) ? l1 : l2最终返回另一个链表递归法入口的第一个 if 直接返回。很多新手没写空值判断一跑就是空指针异常。另一个边界是单节点链表比如 l1[1]l2[2]期望结果 [1,2]l1[2]l2[1]期望结果 [1,2]l1[1]l2[1]期望结果 [1,1]。这些用例看着简单却能把比较符号写错、节点接错的问题暴露出来。测试用例l1l2期望结果说明空链表nullnullnull两个都不存在节点单边空[1,3]null[1,3]原样返回单节点[1][2][1,2]基本顺序相等值[1,3][1,2][1,1,2,3]稳定性检查负数[-3,-1][-2,0][-3,-2,-1,0]负数不影响比较我建议你把这五种用例全部跑一遍再跑一个随机生成的大数据用例比如两个长度各 10000 的有序数组生成链表。如果前四种都通过大概率常规提交没问题大数据用例则用来验证空间和性能尤其是递归法会不会爆栈。4.2 相同值、负数和大量数据的处理如果两个链表包含相同值比如 [1,3,5] 和 [1,2,6]合并结果应该是 [1,1,2,3,5,6]。用还是不影响最终序列但用会让来自 l1 的 1 排在 l2 的 1 前面。稳定排序的好处是行为可预测。如果后续改成合并三个以上链表稳定的取源策略能减少随机性方便排查问题。负数和正数一样处理有序性才是核心数值符号不影响大小比较。但如果你处理的不是整数而是自定义对象就要提供比较器。这个题目在工程里经常退化为“按时间戳合并多条有序记录流”此时节点里存的是对象比较逻辑可能很复杂不过合并框架完全一样。“有序”不一定是自然数值序只要你能提供一个确定的大小判断归并逻辑就能跑。大量数据时优先迭代。我实测过本地环境默认栈大概几百 KB 到几 MB链表长度达到几万级时递归法很容易爆栈。所以做嵌入式、后端批处理这类长链表场景迭代是更稳的选择。如果你必须用递归可以提前检查链表长度超过阈值就走迭代分支做一个 hybrid 版本。4.3 指针遗漏与断链调试技巧我见过的高频错误大概有四类。第一类是 l1 和 l2 同时前进导致跳过一个节点比如把移动指针的代码错误地写在 if/else 外面。第二类是 tail 忘记前进结果所有节点都接到同一个节点后面最后结果链表只剩两个节点。第三类是返回了 dummy 而不是 dummy.next把哨兵节点的值带出来了。第四类是递归版本里修改了 l1.next 之后第二次调用同一函数时发现原始链表结构已经变了。调试这种问题不要只靠眼睛读代码。我一般会在循环里打印当前 tail 指向的值和 l1/l2 的当前值比如System.out.println(tail tail.val , l1 (l1 null ? null : l1.val) , l2 (l2 null ? null : l2.val))。看一眼输出就能定位是哪一步指针没有按预期移动。更高阶的做法是写一个将链表转成列表的辅助函数每次循环结束后打印当前结果链表人工推演一遍最终形态很快能找到断链位置。还有一个技巧每写完一次就故意把某一条链表的头节点替换为 null 再跑一遍确认没有空指针异常。这个习惯帮我省下的调试时间远比想象中多因为它把最常见的边界点从“想当然”变成了“肌肉记忆”。4.4 参数、返回值与内存模型很多人忽略一个问题dummy节点本身也是堆上分配的一个节点。在 Java 里函数返回后 dummy 变成不可达对象自动垃圾回收没问题。但在 C 语言里如果你手动 malloc 了 dummy就需要考虑何时 free。要注意不能把 dummy 和结果链表的真实节点混在一起释放否则可能出现 double free 或悬垂指针。实际工程里我更倾向于让调用方提供输出链表的头节点指针或者约定好返回值由谁负责释放避免内存管理责任不清。在面试中你可以主动提一句“这个解法会改变原链表节点的 next如果不允许改变需要额外复制”这很容易给面试官留下好印象。因为在真实的代码评审里函数有没有副作用远比代码能不能跑过用例重要。5. 从这道题延伸出去K路归并、循环链表与跨表合并5.1 合并 K 个有序链表从两两归并到多路归并面试进阶几乎必问不是两个有序链表而是 K 个有序链表怎么合并。最朴素的做法是顺序两两合并先合并第 1、2 个结果再和第 3 个合并依此类推。假设 K 个链表平均长度都是 L第一次合并后长度为 2L第二次合并长度为 3L总比较次数约 L2L...KL O(K²L)。K 很小时这没问题K 到达几十上百时就要用更高效的多路归并。更好的做法是使用优先队列最小堆。把 K 个链表的当前头节点都放进堆循环弹出最小节点然后把该节点的 next 塞回堆里。每个节点进堆出堆一次堆操作复杂度 O(log K)总复杂度 O(KL log K)。代码上要注意堆里不能放 null 节点每次弹出后要检查 next 是否存在。如果 K 不大两两归并也可以接受K 大时堆方案更稳。这道双链表合并其实是理解 K 路归并最基础的一步。5.2 从单链表到循环单链表合并时要注意什么热词里经常能看到“循环单链表”。它和普通单链表最大的区别是尾节点的 next 不指向 null而是指回头节点。合并两个循环单链表时核心难点不是数值比较而是结束条件的判断。普通链表用while (l1 ! null l2 ! null)就能控制循环循环链表则需要先找到两个链表的尾节点把其中一个的尾节点接到另一个头节点前同时保持首尾闭合。本质上比普通链表归并多了一步“断开再接环”的结构处理。如果没把循环链表的尾节点识别清楚循环条件很难写一不小心就陷入无限循环。嵌入式链表题目里经常埋这个坑因为内核链表大量使用循环链表链表的所有权管理和边界判断要求都很高。我的建议是先把循环链表“展开”成普通链表来思考找到尾节点并临时把 next 置空合并完成后再恢复成环。这是一个实战里非常好用的技巧。5.3 跨表合并与嵌入式链表链表合并不止于面试题“跨表合并”这个词在数据库优化、日志聚合、多路归并排序里很常见。凡是多个有序数据流合成一个有序数据流归并算法都是最直接的选择。我举一个日志归并的例子系统里有多个采集模块各自按时间戳维护一个有序日志链表展示层需要按时间戳合并成一条完整时间线。每次展示时调用合并例程思路和这题完全一致。如果你搜过 git 分支合并、Maven 本地仓库合并这类话题会发现它们更像是树合并、索引合并或集合合并和链表归并不是一回事但理解“两个有序流合成一个有序流”的思想后面对那些复杂合并场景时也会有一个清晰的基础模型。嵌入式领域里双向循环链表极其常见节点的组织方式和刷题版单链表很不一样。合并两条内核链表时不是比大小移动节点而是把一条链表的头尾指针嫁接到另一条链表里核心还是“先记住后继再修改指针”。如果你只会写刷题版单链表到真实内核链表会懵因为节点里可能根本没有 val 字段操作的全是指针区的增删改查。这种“先备份再接线”的思想和合并两个有序链表完全同源。所以这道题不是刷完就扔的题库碎片它是很多工程操作的思维底座。5.4 稳定性与可读性建议工程里写链表合并我一般会遵守几条约定。函数命名要体现排序依据比如mergeAscList避免笼统的merge。函数签名里注明输入是否会被修改用注释明确副作用。不要直接改入参除非调用方明确允许否则做节点复制或快照。单元测试覆盖空链表、单节点、重复值、超长链表四类场景。多写几行防御代码不丢人线上环境里空指针事故带来的代价远比多打几个 if 要高。如果你真的需要频繁合并可以把这部分封装成工具函数输入输出都用不可变快照减少调用方对原链表的意外修改。链表本身是一种底层数据结构越接近系统边界越要小心资源释放和副作用。这道题表面上是算法题实际上是在训练你对“指针即关系”的理解。这道题我前前后后写了不下几十遍每次面试前还会默写一次不是因为它难而是因为它能逼我把边界条件、哨兵节点、迭代递归、复杂度这些基础打扎实。说实话刷题数量并不等于能力能在一个最简单的题目里把每个细节讲清楚才是真懂了。如果你刚开始学链表我建议把这道题作为第一个手写目标先迭代、再递归、然后尝试改写成合并 K 个链表。写完之后你会发现后续的链表反转、排序、插入、删除都会顺很多。最后再分享一个习惯每写完一次就故意把某一条链表置空再跑一遍确认没有空指针异常。这个习惯帮我省下的调试时间远比想象中多。 
长河君 · 2026/10/7 21:44:07 · 阅读 1.2k 合并有序链表全解析：哨兵节点、迭代递归与K路归并
如果你面试前只打算认真看一道链表题那大概率就是“合并两个有序链表”。这个题目的描述很简短给定两个已经按升序排列的单链表把它们合并成一个新的升序单链表并返回。它看起来简单却是我从面试官视角最爱用的题目之一因为短短十几行代码里能同时看出一个人对指针操作、边界条件、递归思维和复杂度分析的熟悉程度。不管你是准备校招、社招还是在日常开发里想补一补数据结构底子这道题都值得从头到尾手写一遍。很多人刷题时习惯直接看答案看过就以为自己会了结果到了白板面试环节一个 dummy 节点都说不清。这里不会只贴一份可运行代码而是想把你最需要理解的几个点拆开讲清楚为什么“有序”是突破口、为什么要用哨兵节点、递归终止条件怎么设计、空链表怎么处理以及合并 K 个链表时怎么复用这里的思路。代码示例会同时给 Java、Python 和 C 语言版本三种语言各有各的脾性但核心逻辑完全一致。无论你主力语言是哪一种建议至少把迭代法和递归法各默写一遍。1. 先把题目拆明白合并两个有序链表到底在考什么1.1 题目描述与选项误区两个输入链表都是非递减有序的这一句话里藏着很多信息。首先链表可以为空空链表不是非法输入而是一种正常边界。其次非递减意味着相等的节点可以连续出现排序结果允许重复值。很多人第一次做这道题第一反应是把两个链表的所有节点值取出来放进数组再统一排序最后重建链表。这个思路能跑通但完全没利用题目给的条件时间复杂度至少是 O((nm)log(nm))空间复杂度也高面试官看到这种答案大概率会追问一句“能不能不用排序”。第二个常见误区是把合并和拼接混为一谈。直接l1尾.next l2是不行的因为 l2 内部虽然有序但 l1 的所有元素未必都比 l2 的第一个元素小。只有逐节点比较并穿插才能保证全局有序。第三个误区是觉得链表操作可以用数组替代甚至想先把链表转成字符串再处理。链表不是数组它没有随机访问能力也不应该为了合并而改变最本质的链式结构。正确的做法是在原节点基础上调整 next 指针在 O(1) 额外空间内完成归并而不是创造一批临时对象再复制一遍。1.2 “有序”二字为什么是破题关键因为有序所以你可以做线性归并不需要回头访问任何节点。类比一个场景手上有两副已经按点数排好的扑克牌现在要合成一副新牌你会把两副牌最上面一张都比较一下拿走较小的那张然后继续比较各自新的最上面一张。整个过程不会回头去翻已经拿走的牌因为你已经通过“有序”确认过当前这轮拿出的牌一定比后续所有待处理牌都小。把这个类比翻译成链表操作就是两个指针 l1 和 l2 分别指向两个链表的当前头节点。每次比较 l1.val 和 l2.val取较小的节点接到结果链表尾部并把对应链表的指针后移一位。由于两个链表自身有序后继节点一定不小于当前节点所以这种贪心选择是全局正确的。最终某一方先走到头另一方剩下的节点天然有序直接整体接上即可。有序性把“排序”降维成了“归并”时间复杂度也被压到线性的 O(nm)。这也是合并操作能成为归并排序、外部排序、多路数据流合并等算法基石的原因。1.3 链表遍历与指针移动的基本功写合并之前先确认链表遍历你真的熟。经典遍历模板是while (cur ! null) { ... cur cur.next; }。不熟的人写合并时常出两个问题一是 while 条件写成了while (cur.next ! null)导致最后一个节点没被处理二是移动指针时顺序错了比如先改了tail.next再把l1后移结果把 l1 的后续链表整个弄丢。链表节点之间的关系只靠 next 维系丢失一个指针就可能让一大段节点变成不可达对象。我建议你先写一个辅助函数遍历两个链表并打印每个节点值。能顺利输出再开始写合并。这一步看似基础却能避免所有因指针移动顺序导致的连环 bug。链表题里最常见的翻车现场就是“我以为断的是这条链结果断的是另一条”所以任何涉及xx.next yy的代码都要在心里问一句原来xx.next指向谁现在它被改掉了有没有别的地方还依赖这个旧引用2. 写代码前必须想清楚的三个细节节点、哨兵和递归出口2.1 链表节点的几种定义写法先统一节点结构。C 语言里最常见的就是struct ListNodeJava 里是ListNode类Python 则用class Node。语言不同核心字段却一模一样一个保存值的val一个保存下一个节点引用的next。下面给出三种常见写法方便你直接对照。public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } }class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextstruct ListNode { int val; struct ListNode *next; };很多语言标准库里的链表节点还会带prev指针形成双向链表但合并有序双链表的逻辑与单链表几乎没有差别只是额外多维护一条prev链路。刷题时先以单链表为准理解 next 的指向变化就够了。工程上如果自己封装链表记得把构造函数也写完整否则每次创建节点都要手动赋值很容易漏字段。2.2 哨兵节点避免头指针判空地狱这是我强调最多的一点。合并过程中你根本不知道结果链表的头节点最终来自 l1 还是 l2因为两个链表元素大小是交错的。如果不用哨兵节点每次添加节点前都要判断result null代码会多出一堆分支而且边界条件特别容易写错。哨兵节点是一个值无关紧要的占位节点通常叫dummy它的 next 最终指向结果链表的真实头节点。用代码讲就是ListNode dummy new ListNode(-1); ListNode tail dummy;之后所有新节点都接在tail.next上并且tail不断后移。循环结束后返回dummy.next。这样做有两个直接好处第一不需要单独处理“结果链表最初为空”的情况因为dummy本身让尾部一直有一个可挂接的锚点第二循环结束时无论哪条链表先耗尽你都能直接拿到结果起点。这个技巧不是这道题独有链表的删除、反转、两两交换等题目里都一样好用可以说是链表操作的万能起手式。2.3 递归解法的终止条件设计递归写法的核心是把大问题缩小成“一个节点加一个小问题”合并 l1 和 l2等价于比较两个头节点取较小者 x然后让x.next merge(x所在链表的剩余部分, 另一条链表)。这个思路很优雅但递归必须有明确的终止条件。合并两个有序链表只有两个终止条件l1 为空返回 l2l2 为空返回 l1。很多人写递归时只记得主逻辑忘记在函数入口判断空链表结果要么空指针要么栈溢出。终止条件的顺序也有讲究。先判断 l1 是否为空再判断 l2 是否为空两者都为空时前一个判断已经会返回 l2此时 l2 也是 null所以不需要额外写第三个 if。如果你把“两者都为空”单独抽出来逻辑上没错但代码冗余。递归在这里虽然代码短但要注意它会有 nm 层递归调用。链表特别长时比如几万个节点递归很可能栈溢出。C 语言默认栈空间有限嵌入式开发里栈空间更紧张所以递归写法更多是展示思维工程落地优先迭代。2.4 迭代与递归怎么选这道题两种写法面试时都要会。如果候选人只写了递归我会追问迭代写法只写了迭代我会追问递归写法。原因很简单递归展示的是把大问题拆成小问题的能力迭代展示的是对指针和内存的掌控力。实际工程里我更倾向于迭代理由有三个。第一递归调用栈深度等于链表长度长度为几万时可能爆栈第二递归会原地修改传入节点的 next调用方可能不希望原链表被改变第三迭代代码虽然没有递归优雅但控制流更直白更容易做断点调试。不过递归版本确实很精练也只有短短几行作为思路验证和单元测试对照非常有价值。如果你在写递归时觉得大脑过载可以先写迭代再把迭代里“更新 tail 并移动指针”的部分替换成“递归调用并返回头节点”转换起来会顺很多。3. 迭代法与递归法逐行实现附完整代码和复杂度分析3.1 迭代法从头到尾谁小接谁迭代法完整代码如下以 Java 为例public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(-1); ListNode tail dummy; 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; }逐行拆开看。dummy的值随便填常用 -1 或 0因为最终会跳过这个节点。tail永远指向结果链表的最后一个节点初始时指向dummy。while条件是“两个链表都还没走完”只要有一个走完循环就结束。比较时取较小节点接到tail.next然后只移动对应链表的指针。为什么只动一边因为较小节点被取走后它的链表需要补充下一个候选节点而另一边的头节点依然留在原位参与下一轮比较。每一步比较后tail都要前进一位否则后续节点会全部覆盖到同一个 next 上。循环结束后最多只剩一条链表还有剩余。剩余链表本身已经有序并且它的当前头节点一定大于结果链表当前的尾节点所以直接把tail.next指向剩余链表的头节点即可不需要再逐节点复制。最后返回dummy.next跳过哨兵节点得到真正的结果头节点。很多人写完后会忘记tail tail.next或者返回时写成了return dummy这两种错误几乎占了链表题提交失败的一半。Python 版本逻辑完全一样只是语法上更简洁def merge_two_lists(l1: ListNode, l2: ListNode) - ListNode: dummy ListNode() tail dummy while l1 and l2: if l1.val l2.val: tail.next l1 l1 l1.next else: tail.next l2 l2 l2.next tail tail.next tail.next l1 or l2 return dummy.nexttail.next l1 or l2是处理剩余节点的简写如果 l1 非空就接 l1否则接 l2。如果你担心可读性写成显式条件也一样。Python 里注意节点对象默认不是空值所以条件判断直接写while l1 and l2即可不需要写l1 is not None。3.2 递归法把“合并”拆成“一个节点再合并”递归法完整代码如下public ListNode mergeTwoLists(ListNode l1, 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; } }入口必须先判断空链表这既是终止条件也是处理边界输入的唯一出口。接着比较头节点值。如果 l1 较小那么 l1 一定是合并结果的头节点它的 next 应该等于“l1.next 与完整 l2 合并”的结果反之 l2 较小就把 l2 作为头节点递归合并 l1 与 l2.next。这样每层递归只确定一个头节点下一层处理剩余链表直到某一条链表为空。递归写法最大的坑是“修改了原节点”。l1.next mergeTwoLists(l1.next, l2)这行代码会直接改写 l1 原始链表里的 next 指针。如果调用方后续还要用原链表做别的事结果就会出问题。你在面试时最好主动问一句“题目允不允许改变原链表结构”如果允许递归没问题如果不允许就需要复制节点或者改用“先遍历到数组再重建链表”的方案。递归的时间复杂度也是 O(nm)但空间复杂度是 O(nm)因为递归调用栈要保存每一层状态。3.3 时间复杂度与空间复杂度怎么算迭代法每一轮循环比较并移动一个节点最多处理 nm 个节点时间复杂度 O(nm)。过程中只用了 dummy 和 tail 两个额外指针空间复杂度 O(1)这是最优的原地操作不依赖链表长度。递归法时间复杂度同样 O(nm)因为每个节点最多被比较一次但空间复杂度不是 O(1)而是 O(nm)它来自递归调用栈。面试时说出这个差异很加分能说明你不是只会背代码。这里再补充一个容易被忽略的细节无论迭代还是递归最坏情况都是两个链表长度接近且元素交替大小比如 l1 [1,3,5]l2 [2,4,6]这样每一轮都要比较共执行 nm-1 次比较。如果其中一个链表非常短比如 l2 只有 1 个节点循环会提前结束剩余部分整体挂接实际比较次数接近 n 次远小于 nm。但这个差异不影响大 O 复杂度评估只影响常数因子。4. 边界条件与调试实录空链表、相等值和指针断链4.1 空链表与单节点链表边界条件能不能考虑全是这道题拉开差距的关键。先说最常见的两个输入都可能为 null。这时候迭代法 while 循环直接不进tail.next (l1 ! null) ? l1 : l2最终返回另一个链表递归法入口的第一个 if 直接返回。很多新手没写空值判断一跑就是空指针异常。另一个边界是单节点链表比如 l1[1]l2[2]期望结果 [1,2]l1[2]l2[1]期望结果 [1,2]l1[1]l2[1]期望结果 [1,1]。这些用例看着简单却能把比较符号写错、节点接错的问题暴露出来。测试用例l1l2期望结果说明空链表nullnullnull两个都不存在节点单边空[1,3]null[1,3]原样返回单节点[1][2][1,2]基本顺序相等值[1,3][1,2][1,1,2,3]稳定性检查负数[-3,-1][-2,0][-3,-2,-1,0]负数不影响比较我建议你把这五种用例全部跑一遍再跑一个随机生成的大数据用例比如两个长度各 10000 的有序数组生成链表。如果前四种都通过大概率常规提交没问题大数据用例则用来验证空间和性能尤其是递归法会不会爆栈。4.2 相同值、负数和大量数据的处理如果两个链表包含相同值比如 [1,3,5] 和 [1,2,6]合并结果应该是 [1,1,2,3,5,6]。用还是不影响最终序列但用会让来自 l1 的 1 排在 l2 的 1 前面。稳定排序的好处是行为可预测。如果后续改成合并三个以上链表稳定的取源策略能减少随机性方便排查问题。负数和正数一样处理有序性才是核心数值符号不影响大小比较。但如果你处理的不是整数而是自定义对象就要提供比较器。这个题目在工程里经常退化为“按时间戳合并多条有序记录流”此时节点里存的是对象比较逻辑可能很复杂不过合并框架完全一样。“有序”不一定是自然数值序只要你能提供一个确定的大小判断归并逻辑就能跑。大量数据时优先迭代。我实测过本地环境默认栈大概几百 KB 到几 MB链表长度达到几万级时递归法很容易爆栈。所以做嵌入式、后端批处理这类长链表场景迭代是更稳的选择。如果你必须用递归可以提前检查链表长度超过阈值就走迭代分支做一个 hybrid 版本。4.3 指针遗漏与断链调试技巧我见过的高频错误大概有四类。第一类是 l1 和 l2 同时前进导致跳过一个节点比如把移动指针的代码错误地写在 if/else 外面。第二类是 tail 忘记前进结果所有节点都接到同一个节点后面最后结果链表只剩两个节点。第三类是返回了 dummy 而不是 dummy.next把哨兵节点的值带出来了。第四类是递归版本里修改了 l1.next 之后第二次调用同一函数时发现原始链表结构已经变了。调试这种问题不要只靠眼睛读代码。我一般会在循环里打印当前 tail 指向的值和 l1/l2 的当前值比如System.out.println(tail tail.val , l1 (l1 null ? null : l1.val) , l2 (l2 null ? null : l2.val))。看一眼输出就能定位是哪一步指针没有按预期移动。更高阶的做法是写一个将链表转成列表的辅助函数每次循环结束后打印当前结果链表人工推演一遍最终形态很快能找到断链位置。还有一个技巧每写完一次就故意把某一条链表的头节点替换为 null 再跑一遍确认没有空指针异常。这个习惯帮我省下的调试时间远比想象中多因为它把最常见的边界点从“想当然”变成了“肌肉记忆”。4.4 参数、返回值与内存模型很多人忽略一个问题dummy节点本身也是堆上分配的一个节点。在 Java 里函数返回后 dummy 变成不可达对象自动垃圾回收没问题。但在 C 语言里如果你手动 malloc 了 dummy就需要考虑何时 free。要注意不能把 dummy 和结果链表的真实节点混在一起释放否则可能出现 double free 或悬垂指针。实际工程里我更倾向于让调用方提供输出链表的头节点指针或者约定好返回值由谁负责释放避免内存管理责任不清。在面试中你可以主动提一句“这个解法会改变原链表节点的 next如果不允许改变需要额外复制”这很容易给面试官留下好印象。因为在真实的代码评审里函数有没有副作用远比代码能不能跑过用例重要。5. 从这道题延伸出去K路归并、循环链表与跨表合并5.1 合并 K 个有序链表从两两归并到多路归并面试进阶几乎必问不是两个有序链表而是 K 个有序链表怎么合并。最朴素的做法是顺序两两合并先合并第 1、2 个结果再和第 3 个合并依此类推。假设 K 个链表平均长度都是 L第一次合并后长度为 2L第二次合并长度为 3L总比较次数约 L2L...KL O(K²L)。K 很小时这没问题K 到达几十上百时就要用更高效的多路归并。更好的做法是使用优先队列最小堆。把 K 个链表的当前头节点都放进堆循环弹出最小节点然后把该节点的 next 塞回堆里。每个节点进堆出堆一次堆操作复杂度 O(log K)总复杂度 O(KL log K)。代码上要注意堆里不能放 null 节点每次弹出后要检查 next 是否存在。如果 K 不大两两归并也可以接受K 大时堆方案更稳。这道双链表合并其实是理解 K 路归并最基础的一步。5.2 从单链表到循环单链表合并时要注意什么热词里经常能看到“循环单链表”。它和普通单链表最大的区别是尾节点的 next 不指向 null而是指回头节点。合并两个循环单链表时核心难点不是数值比较而是结束条件的判断。普通链表用while (l1 ! null l2 ! null)就能控制循环循环链表则需要先找到两个链表的尾节点把其中一个的尾节点接到另一个头节点前同时保持首尾闭合。本质上比普通链表归并多了一步“断开再接环”的结构处理。如果没把循环链表的尾节点识别清楚循环条件很难写一不小心就陷入无限循环。嵌入式链表题目里经常埋这个坑因为内核链表大量使用循环链表链表的所有权管理和边界判断要求都很高。我的建议是先把循环链表“展开”成普通链表来思考找到尾节点并临时把 next 置空合并完成后再恢复成环。这是一个实战里非常好用的技巧。5.3 跨表合并与嵌入式链表链表合并不止于面试题“跨表合并”这个词在数据库优化、日志聚合、多路归并排序里很常见。凡是多个有序数据流合成一个有序数据流归并算法都是最直接的选择。我举一个日志归并的例子系统里有多个采集模块各自按时间戳维护一个有序日志链表展示层需要按时间戳合并成一条完整时间线。每次展示时调用合并例程思路和这题完全一致。如果你搜过 git 分支合并、Maven 本地仓库合并这类话题会发现它们更像是树合并、索引合并或集合合并和链表归并不是一回事但理解“两个有序流合成一个有序流”的思想后面对那些复杂合并场景时也会有一个清晰的基础模型。嵌入式领域里双向循环链表极其常见节点的组织方式和刷题版单链表很不一样。合并两条内核链表时不是比大小移动节点而是把一条链表的头尾指针嫁接到另一条链表里核心还是“先记住后继再修改指针”。如果你只会写刷题版单链表到真实内核链表会懵因为节点里可能根本没有 val 字段操作的全是指针区的增删改查。这种“先备份再接线”的思想和合并两个有序链表完全同源。所以这道题不是刷完就扔的题库碎片它是很多工程操作的思维底座。5.4 稳定性与可读性建议工程里写链表合并我一般会遵守几条约定。函数命名要体现排序依据比如mergeAscList避免笼统的merge。函数签名里注明输入是否会被修改用注释明确副作用。不要直接改入参除非调用方明确允许否则做节点复制或快照。单元测试覆盖空链表、单节点、重复值、超长链表四类场景。多写几行防御代码不丢人线上环境里空指针事故带来的代价远比多打几个 if 要高。如果你真的需要频繁合并可以把这部分封装成工具函数输入输出都用不可变快照减少调用方对原链表的意外修改。链表本身是一种底层数据结构越接近系统边界越要小心资源释放和副作用。这道题表面上是算法题实际上是在训练你对“指针即关系”的理解。这道题我前前后后写了不下几十遍每次面试前还会默写一次不是因为它难而是因为它能逼我把边界条件、哨兵节点、迭代递归、复杂度这些基础打扎实。说实话刷题数量并不等于能力能在一个最简单的题目里把每个细节讲清楚才是真懂了。如果你刚开始学链表我建议把这道题作为第一个手写目标先迭代、再递归、然后尝试改写成合并 K 个链表。写完之后你会发现后续的链表反转、排序、插入、删除都会顺很多。最后再分享一个习惯每写完一次就故意把某一条链表置空再跑一遍确认没有空指针异常。这个习惯帮我省下的调试时间远比想象中多。