1. 双链表合并为什么比单链表更值得单独写一篇如果你刷过链表相关的算法题大概率和我有一样的感受单链表的合并几乎是“新手村”难度两个指针来回比大小谁小接谁代码十几行就能搞定。但题目换成双链表写着写着就开始不对劲——你发现不仅要管next还得管prev一个没注意链表就从中间“劈叉”了。先说清楚这篇博文要解决的问题给定两个已经按升序排列的双链表把它们合并成一个新的升序双链表要求不破坏原始数据并且最终结果依然是一个完整、合法的双链表每个节点都能通过prev正确回溯到头节点。这个能力在真实工程里非常常见比如跨表数据的归并展示、多个有序日志流的合并、内存中双向缓存队列的整合本质上都是这套逻辑。1.1 从“跨表合并”开始聊这个算法到底解决什么问题很多人一看到“双链表合并升序”第一反应是“这不就是归并排序的merge阶段吗”。对但也不全对。归并排序里的merge处理的是数组数组合并只要开一块新空间按顺序填进去就行。但链表不一样链表的节点是散落在内存各处的你要做的是“重新编排节点之间的引用关系”而不是物理搬运数据。我在网上经常看到有人把“双链表合并”和“数组双指针归并”混为一谈实际上两者的思维模式有本质区别数组归并比大小、填新数组、移动下标链表归并比大小、摘节点、挂到新链尾、维护双向指针。后者多出来的一步“维护双向指针”就是双链表合并的核心难点。单链表只需要照顾next一个方向双链表则要求你同时照顾prev和next两个方向。任何一个方向断了最终遍历的时候就会出问题——轻则漏节点重则死循环。再举一个贴近日常的例子你维护着两个升序的用户ID列表一个是VIP用户一个是普通活跃用户现在要做跨表合并生成一份新的展示列表。用双链表来组织这份展示列表前后翻页都方便。这时候你如果直接“照着单链表的思路”合写完一跑前进遍历正常后退遍历就乱了。这就是双链表合并为什么值得单独写一篇的原因——它考察的不是“你会不会比大小”而是“你懂不懂双向结构的完整性”。1.2 双链表的“额外负担”prev指针带来的三处暗坑我先给结论后续每个坑都会展开讲。双链表相比单链表合并时需要额外处理三件事第一摘下的节点挂到新链表尾部时必须同时设置它的prev和next。很多人在循环里写tail-next cur却忘了cur-prev tail结果链表变成了“单向的”后退遍历直接回到空指针。第二原链表被拆空之后最后一个节点的next必须置空。有人会问原来的链表是升序排列的最后一个节点的next本来就是空啊但注意合并过程中这个节点可能不是最后一个它可能中间被挂到了新链上它的next还残留着指向原链表下一个节点的地址。如果不手动置空新链表最后会“拖着一截不该出现的尾巴”。第三移动指针时prev的指向更新必须和next同步。链表里移动curA curA-next很容易但如果你在移动前把某个节点的prev改了又没同步好整个链就拧了。这三个坑我分别会在第3章、第4章和第6章具体演示。先把数据和结构准备好咱们一步步来。2. 动手前的数据准备双链表的节点定义与尾插法构建代码写得好不好很多时候一开始的结构设计就决定了。双链表合并这个题目节点定义和构建方式有一定讲究尤其是你打算在面试或考试环境下手写代码的时候结构设计是否简洁直接决定了后面合并函数能不能写得流畅。2.1 节点结构到底该怎么设计带头结点vs不带头结点双链表节点最经典的定义长这样struct ListNode { int val; ListNode* prev; ListNode* next; ListNode(int x) : val(x), prev(nullptr), next(nullptr) {} };注意我在这里用了prev而不是prior或者其他命名。命名本身不重要重要的是你要习惯一套固定的命名写起来不容易乱。我见过有人用pre有人用previous都行但别写着写着混了。接下来是“带头结点”和“不带头结点”的选择分歧。头结点dummy head是一个不存储有效数据的哨兵节点它的next指向第一个真正有数据的节点。我强烈建议面试和笔试场景一律带头结点。原因很简单带头结点后链表为空时头结点的next为nullptr不需要特判插入第一个节点时不需要单独处理“头指针为空”的情况合并时用哑结点做新链的头最后直接返回哑结点的next代码统一且少出错。如果你习惯不带头结点的写法也能做只是边界条件会多一些。比如在空链表上插入第一个节点你得先判断head nullptr然后手动把head赋给新节点。代码会多出至少三个if。对于这种已经有不少注意力要花在prev维护上的题目能少一个特判就少一个。2.2 尾插法构建双链表顺带处理升序输入给定一个升序数组构建对应升序双链表最稳的方式是尾插法每次生成新节点挂在当前链表的尾部同时维护好prev和next。ListNode* buildDoublyLinkedList(const vectorint nums) { ListNode* dummy new ListNode(0); ListNode* tail dummy; for (int val : nums) { ListNode* node new ListNode(val); tail-next node; node-prev tail; tail node; } return dummy; }这段代码有两点值得注意一是tail-next node; node-prev tail; tail node;这三行是尾插双链表的标准“三步走”。顺序不能乱。先挂next再挂prev最后移动tail。如果你先做了tail node那tail-next就挂了后面的node-prev也会错。二是返回的是dummy头结点而不是第一个有效节点。合并函数里我们也要用哑结点两个哑结点概念不冲突——一个是原链表的头一个是新链表的头。构建完成后一个例子是这样的1 ⇄ 3 ⇄ 5对应的存储结构是dummy.next 1号节点1号节点.prev dummy1号节点.next 3号节点3号节点.prev 1号节点3号节点.next 5号节点5号节点.prev 3号节点5号节点.next nullptr。2.3 一个连排序都没有的“假升序”如何在构建时就埋下雷这里我想插一个真实踩过的坑。早期我图省事构建双链表用的不是尾插法而是“从前往后”的头插法然后逆序存储。结果测试合并的时候跑出来全是“降序”的。原因很简单头插法每次把新节点插到最前面假设依次插入1, 3, 5最终链表顺序是5 → 3 → 1完全反了。我当时还在奇怪为什么合并结果总是从大到小排查了半小时才意识到是构建过程的问题。后来我养成一个习惯无论题目给的数据是升序还是降序构建完链表先从头到尾走一遍打印每个节点的值确认顺序没反再做合并。这个“打印自查”的习惯在调试链表类题目时性价比极高后面第6章我还会详细说。3. 升序合并的核心算法哑结点双指针的完整拆解数据准备好了现在进入正题。假设我们有两个升序双链表listA和listB目标是合并成一个升序双链表result。3.1 整体思路归并排序的“合并”阶段整体思路一句话两个链表的头节点分别用一个指针指向每次比较两个指针所指节点的值把值较小的那个节点“摘下来”挂到新链表的尾部然后移动对应指针。循环往复直到其中一个链表被取空再把另一个链表剩余部分一次性接上。这和归并排序里的merge阶段完全同构所以你也可以把它理解为归并排序思想在链式存储结构上的应用。为什么选择这个方案而不是“把两个链表的所有节点收进数组排序再重建链表”当然是因为时间复杂度。归并式合并的时间复杂度是O(n m)其中n和m分别是两个链表的长度。而“先收集到数组再排序”的时间复杂度最坏是O((nm) log(nm))数据量一大差距就出来了。空间复杂度上前者只需要常数级额外空间不算新建的哑结点后者要O(nm)的数组空间。所以不管从时间还是空间上看归并式合并都是这个场景下的最优解。3.2 指针怎么走三条链的顺序维护这一步是整个合并过程的灵魂。我建议你画一张图有三个链表参与curA指向链表A当前正在考察的节点curB指向链表B当前正在考察的节点tail指向新链表的当前末尾节点初始化为哑结点。每一轮比较的逻辑可以用一句话概括curA-val curB-val时把curA指向的节点摘下来接到tail后面否则把curB指向的节点摘下来接到tail后面。“摘下来”这个动作具体有三个子步骤把tail-next指向选中的节点cur把选中的节点的prev指向tail移动tail到选中的节点同时移动cur到原链表的下一个节点。前两步是“建立双向连接”第三步是“更新考察指针”。顺序不能颠倒尤其是第一步和第二步。如果你先做了第三步cur已经指向下一个节点了你手上的“选中节点”就找不到了。这个错误我第6章会重点讲现场写代码的时候特别容易犯。3.3 关键代码C实现带逐行注释直接给出我可以直接拿去刷题的完整 C 实现ListNode* mergeTwoDoublyLinkedLists(ListNode* listA, ListNode* listB) { // 哑结点作为新链表的头部避免处理空链表和首节点插入的特判 ListNode* dummy new ListNode(0); ListNode* tail dummy; // curA 和 curB 分别指向两个链表第一个有效节点 ListNode* curA listA-next; ListNode* curB listB-next; // 两个链表都还有节点时比较并摘取较小者 while (curA ! nullptr curB ! nullptr) { if (curA-val curB-val) { // 摘下 curA先保存它的下一个节点防止移动指针后丢失 ListNode* nextA curA-next; // 把 curA 挂到新链尾 tail-next curA; curA-prev tail; // 注意这里必须把 curA-next 置空否则会残留旧的下一个节点 curA-next nullptr; // 移动 tail 和 curA tail curA; curA nextA; } else { // 对称地处理 curB ListNode* nextB curB-next; tail-next curB; curB-prev tail; curB-next nullptr; tail curB; curB nextB; } } // 如果链表A还有剩余接到新链尾部 if (curA ! nullptr) { tail-next curA; curA-prev tail; // 注意不能再把 curA-next 置空因为剩余部分是整段接入的 } // 如果链表B还有剩余同样接到新链尾部 if (curB ! nullptr) { tail-next curB; curB-prev tail; } // 返回新链表的第一个有效节点 return dummy-next; }这里有一点要特别说明在剩余部分整段接入时不能把curA-next置空。因为剩余部分是一整段链表它的next关系原本就是正确的我们要做的是把这一整段“接在”新链尾部即可。如果你在循环里的curA-next nullptr写习惯了在剩余部分接入时也照做那等于把剩余链表的后半段全砍掉了。3.4 为什么哑结点方案在这里特别好用你可能会有疑问哑结点是不是有点浪费一个节点而已真的有必要吗我给你的回答是在面试环境下哑结点不只是“有必要”而是“非常有帮助”。它最大的价值在于让你不用考虑“新链表第一个有效节点到底该挂在哪个指针后面”。如果你不用哑结点你就得单独处理“第一次选中的节点作为新链表的头”这种特判代码大概会多出六到八行而且这六到八行是错误的高发区。哑结点相当于帮你把这个特判“预支”掉了代价只是一个节点非常划算。另外哑结点方案还有一个额外的好处当两个链表都是空的时候直接返回dummy-next也就是nullptr逻辑自洽不需要任何特殊处理。4. 最容易写错的三个边界prev维护、尾节点置空、长度不等很多代码核心循环写对了最后挂在边界处理上。双链表合并边界有三个“重灾区”每一个我都亲眼见过也亲手写错过。4.1 prev指针的更新时机这是双链表合并和单链表唯一的本质区别单链表的合并只需要一行tail-next cur然后移动指针就行。双链表则必须在挂next的同时挂prev。这个“同时”指的不是时间上的同一行而是逻辑上不可分离的同一组操作。具体来说你应该把下面三行当成一个“原子操作”来记tail-next cur; cur-prev tail; tail cur;第一行建立正向连接第二行建立反向连接第三行移动尾指针。任何一行都不可以单独删掉。我曾经看过一个同学调试的代码输出结果从前往后完全正常但从后往前遍历时第一次向前走就崩了。原因就是他在循环里只写了tail-next cur忘了cur-prev tail。结果这个链表从中间开始所有节点的prev都还是原来的旧值有的指向旧链表的前驱有的指向自己。这个崩溃属于典型的“双向关系不对称”。4.2 两个链表长度不一样剩余节点的衔接长度不等的场景在测试用例里出现频率极高。比如listA有 3 个节点listB有 5 个节点前 3 轮可能就把listA取空了此时curA变成nullptr循环退出。但curB还指向第 4 个节点后面还有两个节点没处理。这部分的处理策略我在第3章的代码里已经写了if (curA ! nullptr)就把剩余的curA整段接入if (curB ! nullptr)就把剩余的curB整段接入。这里最容易出的问题是“整段接入时要不要把剩余链表末端置空”我的答案是不用除非你知道剩余链表的最后一个节点不是真正的链尾。怎么理解curA如果非空那它指向的一定是原链表A当前还未被摘取的第一个节点。这个节点往后一直到 nullptr 的整段链表都是完整的、合法的升序链。你只需要把它接到新链尾部即可它的next关系天然正确。如果你画蛇添足去遍历这个剩余链然后把某个节点的next置空反而会破坏它的结构。但是这里有一个隐藏前提你在循环中摘取节点时必须把被摘节点的next置空。为什么要这样做因为被摘节点在新链表里是“单节点接入”它的next如果不置空就会残留指向原链表下一个节点的指针。等到新链表构建完你从前往后遍历时可能会“顺着残留指针跑回旧链表去”。这正是我在第2章末尾提到的“拖着一截不该出现的尾巴”。4.3 空链表和单节点链表测试时最容易忽略的case我刷题和面试辅导时反复强调一件事写完代码第一件事是拿空链表和单节点链表去“过”一遍逻辑。双链表合并对这个要求更高因为prev的存在让边界情况更隐蔽。举三个具体的空链表场景listA为空listB非空curA一开始就是nullptr循环不进入直接走if (curB ! nullptr)分支把listB整段作为结果。这没问题。listA非空listB为空对称操作。两个都是空循环不进入两个if都不成立返回dummy-next nullptr。这三个场景里最容易出错的是第一个。因为你在循环外写if (curB ! nullptr)的时候可能会因为curB的prev需要更新而想到“要不要把curB原来的头结点prev也改掉”。这里有一个容易被忽略的细节如果listB是不带头结点的原始链表它的头结点的prev可能就是nullptr。整段接入后这个节点的prev应该指向tail否则从新链表尾部往前遍历的时候走到这个节点就断了。所以curB-prev tail;这行在剩余接入中不能省。单节点链表的情况相对简单listA只有 1 个节点和listB循环比一轮就结束了。但你要注意一个细节合并后的链表里这个唯一的节点可能是第一个有效节点也可能是中间的节点。它在不同位置时prev和next的指向完全不同。这就是为什么我强烈建议你合并完直接“正向反向双遍历”验证——不仅从head往tail走一遍还从tail往head走一遍确保所有prev都是合法的。5. 复杂度剖析与面试现场的标准答案写完了代码接下来就是要能“说出个所以然”。这一章帮大家把复杂度分析整理好再附上面试官常见的三个变体追问。5.1 时间复杂度和空间复杂度从循环不变式说清楚时间复杂度是O(n m)其中n是listA的长度m是listB的长度。为什么呢因为在循环体里每一轮我们只处理一个节点要么是curA被摘下要么是curB被摘下。处理完一个节点对应的指针就走一步。两个指针总共会走n m步所以循环体总执行次数是O(n m)。这里有一个值得注意的细节两个链表的总节点数是n m但循环体最多执行n m次而不是n m - 1次。原因是当其中一个链表被取空的“最后一轮”循环条件已经不再满足此时剩余链表直接整段接入不需要再多一轮。空间复杂度是O(1)不考虑新建哑结点。原因是我们没有使用任何与链表长度相关的额外存储只用了几个固定数量的指针变量。新建的哑结点一个不随输入规模增长。读者可能会问新建的节点算不算额外空间严格来说哑结点是O(1)的因为它不随输入规模变化。但如果面试官追问“如果要求原地合并不新建任何节点”你可以回答也可以用同样思路把listA或listB当作结果链表的起点但代码会复杂不少且需要额外处理“谁是头”的问题。面试时优先推荐哑结点版因为它正确率高。5.2 面试官最爱追问的三个变体面试官很少让你直接背代码更多是改条件测试你的理解是否深入。根据我的经验双链表合并最常见的变体有三个变体一不允许新建链表原地合并返回其中一个链表的头。这个变体的核心思路是把listA的头结点当作新链表的哑结点直接在上面做尾插。这样省了一个节点但要注意两个链表的“所有权”混在一起最后返回的是哪一个头取决于谁的值更小。我在实际辅导中建议除非你非常熟练否则面试时还是老老实实用哑结点宁可多一个节点也别把思路绕晕。变体二合并后要求去除重复值。比如listA有1, 3, 5listB有3, 4, 5要求合并结果1, 3, 4, 5。这时在比较相等值的两个节点时需要跳过其中一个。具体做法是当curA-val curB-val时要么释放curA要么释放curB并把对应指针前进一位。或者更粗暴合并后遍历一遍去重。两种做法都能过但“边合并边去重”有一个额外好处——不需要额外的辅助空间。变体三两个链表不是升序而是降序。解法有两种先反转再合并或者把比较符号反过来。但如果你选择了“先反转再合并”要注意反转双链表的复杂度是O(n m)整体依然是线性可以接受。如果你选择“把比较符号反过来”那么curA-val curB-val时摘curA这个逻辑同样正确但面试官可能会继续追问“合并出来的链表是升序还是降序和原来两个链表的顺序有什么关系”答案就是两个都降序合并出来一定是降序两个都升序合并出来一定是升序。5.3 双链表合并 vs 排序后拼接 vs 数组排序三种方案怎么选算法题本质上是在多个可行方案里选最合适的。我整理一个表格把常见的三种合并思路放一起对比方案时间复杂度空间复杂度是否原地适用场景归并式双链表合并O(nm)O(1)是只建哑结点两个链表本身已升序最标准收集到数组排序再重建链表O((nm) log(nm))O(nm)否链表无序或需要额外排序逻辑时单向链表归并思路套用O(nm)O(1)是只需考虑 next 方向不需要回溯的场景从表格可以看出双链表合并的归并式方案在“两个输入链表已升序”的前提下时间和空间都是最优的。如果你在真实工程中遇到了“两个链表各自有序要合成一个有序链表”的需求直接上这套方案没问题。6. 实测排错我调双链表合并时踩过的坑最后这一章我分享三个我在实际调试双链表合并时踩过的坑全都是“看代码看不出来一跑就崩”的典型问题。6.1 经典Bug循环里忘了更新prev结果链表“分叉”这个Bug我前面已经提到过一次但值得单独展开。当时我写的循环长这样while (curA ! nullptr curB ! nullptr) { if (curA-val curB-val) { tail-next curA; // 漏了 curA-prev tail; tail curA; curA curA-next; } }从前往后打印输出完全正常1、3、5、2、4 这种顺序都对。但从后往前打印走到3这个节点时3-prev还是指向它原来在旧链表里的前驱可能是1也可能是空整个回溯链路就断了。更诡异的是因为旧链表里3的后继是5而新链表里3的后继也是5所以有时候“碰巧”不出错但只要两个链表有交叉就会完全乱掉。这个问题怎么排查出来呢我当时的做法是在每个节点上打印它的prev和next的地址然后人工对比。后来我总结出更高效的办法写一个小函数verifyDoublyLinkedList(head)正序遍历一遍再逆序遍历一遍两边的节点个数必须相等且逆序遍历的最后一个节点必须是头节点。这个验证函数我强烈建议你调试链表题时一定写出来毕竟是“苦力活”但能快速定位一半以上的问题。6.2 经典Bug漏掉curA-next nullptr整个链表原地断裂第二个坑和第一个正好相反——我写了curA-prev tail但忘了把curA-next置空。在合并过程中curA原本的下一个节点可能在旧链表里也可能已经被摘走了。如果不置空摘下来的节点在新链表中会“残留”指向旧位置的next导致新链表尾部多出一截“幽灵链”。我记得有一次跑测试合并完打印了 9 个节点但实际新链表里只有 5 个有效节点多出来的 4 个节点来自旧链表里尚未处理的部分。打印结果看起来像“1 3 5 7 9 6 8 10”——前半段新链表正常后半段全是从旧链表“顺藤摸瓜”带出来的。当时我盯着输出看了很久才反应过来问题就出在漏了curA-next nullptr。后来我在代码里特意加了一行注释“摘下来的节点next 必须立刻断干净”。这不是可选项这是保证链表结构完整的必要条件。6.3 调试技巧打印prev的地址看双向关系是否一致最后一个经验是给实在调不出问题的人一个“暴力”手段。如果你发现链表行为异常但正序输出又看不出问题直接写一段代码把所有节点的prev和next的地址都打出来void debugDoublyLinkedList(ListNode* head) { ListNode* cur head; while (cur ! nullptr) { cout node cur-val prev cur-prev next cur-next; if (cur-prev) cout prevVal cur-prev-val; if (cur-next) cout nextVal cur-next-val; cout endl; cur cur-next; } }双链表的美妙之处在于它的结构天然具有“相互验证”能力——如果cur-next-prev ! cur那么这个节点就是对不上的。你可以写一个断言函数来检查这一点bool isDoublyLinkedListValid(ListNode* head) { ListNode* cur head; while (cur ! nullptr) { if (cur-next ! nullptr cur-next-prev ! cur) return false; cur cur-next; } return true; }这个函数一旦返回false基本就能确定是prev或next漏更新了。我个人的习惯是每次写完合并函数跑测试用例之前先跑这个验证函数能省掉大半的 printf 调试时间。我实测下来这套“代码写完先去验证双向一致性再验证升序最后再跑具体用例”的流程已经帮我处理了不下十个链表相关的项目场景包括数据流合并、跨表结果集展示、差量同步列表生成。如果你现在正在准备算法面试或者工作中要处理类似的双链表合并需求按这个流程走一遍能少走很多弯路。