前两天在 AcWing 上刷题看到编号 3639 这题叫“链表合并”乍一看特别基础就是两个单调不减的链表合成一个但真的动手写才发现能在 5 分钟内一次写对的人并不多。很多人不是不会双指针而是栽在空链表、虚拟头结点、尾指针置空这些细节上。这篇文章就把这类题目从头到尾拆开从算法思路讲到代码实现再顺手把循环单链表、链表逆置、跨表合并这些高频变体一并说清。不管你是刚学 C 结构体的新手还是准备机试、校招的选手都能照着练出可用代码。1. 先把题目读懂合并两个有序链表到底在考什么1.1 题面还原与考点拆解AcWing 3639 这道题题面通常会这样描述输入两个按非递减顺序排列的单链表将两个链表合并成一个新的非递减有序链表并返回。输入格式一般是先给两个链表的长度 n 和 m然后分两行给出 n 个整数、m 个整数。输出一行是合并后的链表的全部节点值。例如3 3 1 3 5 2 4 6输出1 2 3 4 5 6题目给定的链表节点结构通常就是最常见的单链表结构每个节点只有一个next指针。函数接口一般是ListNode* mergeTwoLists(ListNode* l1, ListNode* l2);这题表面上只是“把两个链表串起来”但实际上考了三个层次的东西第一个是指针操作的基本功。链表不像数组数组直接按下标读写链表必须通过next指针一个个跳。合并过程中你不能“复制”节点而是要把已有的节点重新接起来这就要保证指针在修改前后都没丢。第二个是边界思维。l1 和 l2 是否为空两个链表长度是否相等节点值相等时谁先谁后每次循环结束后还有没有剩余节点这些边界条件只要漏了一个程序就会在评测机上返回 Runtime Error 或者 Wrong Answer。第三个是复杂度意识。合并两个总长度为 n m 的链表能不能做到只遍历一遍能不能做到不额外申请长度为 n m 的数组能因为链表结构天然适合“原地”修改指针。这也是这道题存在的意义如果只是要合并两个有序序列用数组存然后归并空间复杂度就是 O(n m)而链表可以用 O(1) 额外空间完成。1.2 不额外开空间的归并思路合并有序链表核心思路和数组归并排序中的合并阶段一模一样就是双指针。具体来说我拿两个指针 pa 和 pb 分别指向 l1 和 l2 当前要比较的节点。每一轮比较pa-val和pb-val把值较小的节点接到结果链表的尾部然后让那个指针向后移动一步。继续循环直到其中一条链表先走完。最后另一条链表剩下的节点直接整体接上去因为剩下的节点本来就是有序的。为什么这样不会丢节点因为每一步我们都是“拆”一个节点出来接到新链上被拆节点的下一个节点已经被我们提前记住了比如pa pa-next就是在拆完节点之后立刻把指针挪到下一位相当于把原链表的头节点“切除”了。这个思路可以打个比方合并两个有序链表就像拉一条拉链。左右两排链牙分别对应两个链表每次从哪边选一个更小的节点就是让拉链头往下咬合一个牙位。两排长度可以不相等一边咬完了另一边剩下的直接顺势拉到底。时间复杂度是 O(n m)每个节点最多被比较一次、被接一次。额外空间是 O(1)因为我们只用了几个指针变量没有新建任何链表节点。这就是为什么这道题必须用链表而不是数组来做数组的合并需要额外的存储空间链表不需要。2. 从零手写迭代合并的完整实现2.1 结构体定义与辅助函数在 C 写链表题我习惯先把节点结构体定义好。AcWing 上通常可以直接用题目给定的结构体但本地练习时还是要自己写一份。struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };这里最容易被新手忽略的是构造函数里一定要初始化next。如果写成struct ListNode { int val; ListNode *next; };然后new ListNode出来的节点next是一个随机值不手动置空就等着出 bug。所以我看很多经验帖都会强调链表节点的指针成员必须在创建时初始化为 nullptr哪怕题目不要求也会让你的调试轻松很多。另外我经常在本地写一个buildList函数来快速构造链表方便测试ListNode* buildList(int n) { ListNode dummy(0); ListNode* tail dummy; for (int i 0; i n; i) { int x; cin x; tail-next new ListNode(x); tail tail-next; } return dummy.next; }如果不引入dummy在循环里就得先判断head nullptr再决定是让 head 指向新节点还是让 tail 去接代码判断就会多一层。从这里就能看出虚拟头结点的价值。2.2 双指针主循环直接给出我比较推荐的迭代版写法ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail dummy; while (l1 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 ? l1 : l2; return dummy.next; }我来逐步解释每一行在做什么。ListNode dummy(0);是在栈上创建一个虚拟头结点。这个节点不参与数据它的作用只是为了让结果链表有一个固定的起始位置。tail始终指向当前结果链表的最后一个节点初始时指向dummy。进入while (l1 l2)后只要两条链表都还有节点就比较当前两个节点的值。假设l1-val更小就把l1这个节点接到tail-next上。此时l1已经接到结果链里了不能再当作原链表头指针用所以立刻执行l1 l1-next让l1指向原链表的下一个节点。这个顺序不能反反了就先丢失后继节点了。tail-next l1之后tail也要向后走一步即tail tail-next否则下一次接入会覆盖掉刚接入的节点。循环结束后至少有一条链表已经为空。另一条链表可能还有若干个节点因为剩余部分本身有序可以直接用一行代码接上tail-next l1 ? l1 : l2;这句也叫“剩余链直接续接”。很多人的代码写到这里就漏了导致输出少了后半段。这道题对漏掉这一行的检测是很明显的只要两条链表长度不等结果就会缺。最后返回dummy.next就是合并后链表的第一个有效节点。这里特别注意不能返回dummy本身。2.3 虚拟头结点从“不带头结点”到“带头结点”很多教材里讲链表会区分“带头结点”和“不带头结点的单链表”。这道题给的是不带头结点的单链表头指针直接指向第一个数据节点。不带头结点时如果你直接修改头指针就会遇到一个麻烦第一个节点接入前结果链表的头还为空你需要单独判断“这是不是第一个节点”。比如不用虚拟头结点的写法ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; ListNode* head nullptr; ListNode* tail nullptr; while (l1 l2) { ListNode* cur; if (l1-val l2-val) { cur l1; l1 l1-next; } else { cur l2; l2 l2-next; } if (!head) { head cur; tail cur; } else { tail-next cur; tail cur; } } tail-next l1 ? l1 : l2; return head; }能看出区别吗多了if (!head)这个分支。在循环里每加入一个节点前都要判断头结点是否已经确定。代码一多就越容易出错。使用虚拟头结点之后所有新节点的接入都统一变成tail-next cur不需要判断“当前是不是空链”。这相当于把“不带头结点”的问题人为转换成了“带头结点”的问题。尤其是在一些更复杂的链表操作中虚拟头结点能够成倍减少特判的数量。在 AcWing 这类 OJ 上提交时直接用dummy方式是最稳的因为题目只要求返回“新链表的头指针”没有要求原链表结构保持不变也不存在需要手动释放节点的问题。3. 边界、细节与两个经典变式3.1 空链表、相等值、单个节点链表题写起来容易但挂掉的很多都是边界。我自己合并过几次总结出几个最容易踩的点。第一个是空链表。l1 为空就直接返回 l2l2 为空就返回 l1两个都为空就返回空。用虚拟头结点的写法这些情况其实已经被统一处理了while直接不进tail-next l1 ? l1 : l2会把非空的那个链整体接上。但如果你是手写不带虚拟头结点的版本必须一开始就处理空指针否则后面l1-val或l2-val会直接解引用空指针。第二个是相等值。在比较时我习惯用而不是。用时如果两个链表有相同值的节点会优先取 l1 的节点这种合并是“稳定”的。用时相同值会优先取 l2 的节点结果仍然有序但节点的来源顺序和稳定合并不同。面试时如果面试官追问“如果两个值相等应该怎么处理”至少你要能说出“结果有序性不受影响但稳定性有区别”。第三个是单个节点的极端情况。比如 l1 只有一个 1l2 只有一个 2循环执行一次后 l1 为空tail-next接上 l2结果是 1-2正确。如果 l1 [1]l2 [1]时先接 l1 的 1再接 l2 的 1结果 1-1也正确。我经常提醒自己写完代码后一定先把这几组情况在心里过一遍不要直接去跑全量测试。能在本地排除的边界错误就不要浪费 OJ 的提交次数。3.2 变式一递归写法递归是合并有序链表最常见的另一种写法代码极短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; } }递归的思路是每次取出两个头结点中较小的那个它的next应该指向“剩下的两个链表合并后的结果”然后返回这个较小节点作为合并后的头。这个代码虽然优雅但有一个必须提到的代价递归深度等于合并路径上被选中的节点数量最坏情况下是 O(n m)。如果两个链表的节点总数达到几万甚至十几万递归版在 OJ 上可能直接栈溢出而迭代版完全不受影响。所以我在 AcWing 上提交时首选迭代版只有在面试场合递归版用来展示思路简洁才值得优先写出来。3.3 变式二跨表合并交替合并看热搜词里有人提到“跨表合并”这个词在算法题里通常指不是按值的大小合并而是按位置交替取两个链表的节点生成一条新链表。比如 l1 是 A1 - A2 - A3l2 是 B1 - B2结果变成 A1 - B1 - A2 - B2 - A3。这种合并实现起来也不难用虚拟头结点加一个布尔标记就够了ListNode* interleaveMerge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail dummy; bool takeFirst true; while (l1 l2) { if (takeFirst) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; takeFirst !takeFirst; } tail-next l1 ? l1 : l2; return dummy.next; }这个变式在实际中有什么用我举几个场景比如两个有序的数据流要生成一个新的播放列表交替插入两条队列的内容或者在做某种“轮流调度”时需要把两条任务链表交错合并。虽然面试中考察频率不如有序合并但既然热搜里有这个词说明很多人也在被考到类似的题。注意跨表合并和有序合并的核心差异有序合并的比较条件取决于val跨表合并的比较条件只取决于轮次。代码长得像但逻辑完全不同。所以看题必须先确认题目到底要求按大小还是按位置。4. 链表题的高频扩展从合并到逆置、循环链表4.1 逆置链表与合并的组合拳链表合并经常和链表逆置放在一起考。比如题面变成“将两个链表合并但要求结果按非递增顺序排列”一种很自然的做法就是先按非递减合并再把结果链表整体逆置一遍。链表逆置是另一个基础功三指针迭代法ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur) { ListNode* nxt cur-next; cur-next prev; prev cur; cur nxt; } return prev; }这里最关键的是循环里的第一行ListNode* nxt cur-next;。因为下一步就要修改cur-next如果不提前保存原链表的剩余部分就找不到了。这个“先保存后继再动手”的习惯在处理所有链表修改操作时都通用。合并加逆置的组合题一般不会比单独考两者更难但它能检验你能否把两个基础操作组合调用而不产生 bug。比如先合并再逆置返回值就变成了reverseList(mergeTwoLists(l1, l2))。4.2 循环单链表场景下的合并注意事项有的题目会说“循环单链表”也就是尾节点的next指向头节点而不是nullptr。循环链表的合并比普通链表麻烦不少因为“空”的判断完全变了。普通链表遍历时判断cur nullptr结束循环链表这样写就死循环了。合并两个循环链表时我习惯按三步走先把两个循环链表在头结点处“断开”让尾节点的next置为nullptr把它们变成两条普通的单链表。按普通单链表的合并逻辑处理得到一条普通链表。遍历合并后的链表找到尾节点把尾节点的next指向新的头节点重新形成循环。这三步里最容易踩的坑是第一步。断环必须记住原来的头是谁否则断完之后你以为拿到了头实际可能已经走到别的位置去了。另外要注意长度只有 1 的循环链表断开操作要格外小心避免自己打断自己的唯一链接。有人问“为什么不直接在环上合并”理论上也可以但指针操作更复杂容易出现遗漏。先把循环转成普通链是降低犯错成本的做法。在竞赛或机试中如果题目没有特别要求必须原地在环上操作断环再合并通常更稳妥。4.3 常见进阶合并 K 个有序链表如果把两个链表合并扩展到 K 条有序链表就是更常见的“合并 K 个有序链表”问题。这个题也是很多大厂面试的常客。处理 K 路合并有三种主流思路方案核心做法时间复杂度适用场景顺序两两合并拿第一条和第二条合并结果再和第三条合并循环下去O(K * N)K 很小代码简单分治合并把 K 条链表分成两组每组内合并再两两合并O(N * log K)K 较大适合笔试最小堆把所有链表的当前头结点放入堆每轮弹出最小值并补充后继O(N * log K)需要每步知道最小值适合流式处理对初学的人来说不管用哪种方式最底层的单元仍然是mergeTwoLists这个函数。所以别看 AcWing 3639 只是一个双链表合并它其实是后面所有复杂归并问题的最小积木。我在平时练习时有个习惯每写一个基础函数就想想它能怎么被套进更大的问题。比如合并两个链表学会后再去写 K 路合并时代码量会少很多。5. 调试经验与常见问题排查5.1 最常见的三个 Runtime Error 原因链表题在 OJ 上报错绝大多数是这三个原因。第一个是空指针解引用。典型场景在while (l1)里直接访问l2-val但l2可能已经变成nullptr。或者在不带头结点时刚开始就访问head-val却忘记处理head本身为空。这类错误在本地可能不报错但评测数据一多就原形毕露。第二个是链表成环。有些人在合并过程中改next改乱了比如应该接 l1 的时候错误地接回自己导致输出链表时无限循环OJ 提示“Time Limit Exceeded”。这种 bug 难定位我通常会在本地用一个计数器限制打印长度例如最多打印 1000 个节点如果没结束就说明链表成环了。第三个是返回头指针错误。使用虚拟头结点时如果你写成return dummy返回了一个栈上对象的地址函数结束后该对象生命周期结束调用方拿到的是一个悬垂指针。正确写法是return dummy.next。这里没有删除指针的负担因为dummy是栈上对象不是 new 出来的。5.2 如何自己造测试数据链表题不能只靠题目的样例你必须自己会构造测试用例。我在本地调试时一定会准备这些空链表 空链表确保返回空空链表 非空链表确保返回非空链表两个单元素链表比如 [1] 和 [2]存在相同值的链表比如 [1, 1, 3] 和 [1, 2, 2]长度差异很大的链表比如 l1 有 100 个节点l2 只有 1 个构造好后再用printList验证void printList(ListNode* head) { while (head) { cout head-val ; head head-next; } cout endl; }建议把printList单独封装成一个函数方便在每次操作前后都打印一遍。我调试链表时的一个习惯是“每走一步打印一次”比如合并前打印 l1、l2合并后打印结果。这样能很清晰地看到哪个指针丢了、哪个节点被重复接入。5.3 解题时的“加分”习惯最后聊几个写链表题时容易被忽略的加分习惯。第一命名清晰。l1、l2这种参数名是题目给的没问题但函数内部的指针变量最好叫pa、pb、tail、cur而不是a、b、p。关键代码写给别人看时可读性几乎和正确性一样重要。第二明确入参是否可以被修改。在很多链表题里函数是允许修改两个原链表的但在工程化的场景中调用方可能仍需要保留原链表。这时需要在合并前复制节点或者说明“本操作会修改原始链表”。OJ 题不用考虑这个但面试题里最好主动和面试官确认。第三提交前画一遍小的数据流。在纸上画 3 个节点的链表模拟指针怎么移动能发现很多代码层面注意不到的 bug。尤其是循环链表、链表逆置这类题画图比硬想有效得多。第四时间复杂度和空间复杂度要脱口而出。合并两个有序链表是 O(n m) 时间、O(1) 空间递归版是 O(n m) 空间跨表合并同样是 O(1) 空间。这几乎是一道送分题不要在这个地方卡壳。我个人在实际刷题中的体会是链表合并这个题一定要把迭代版写到“闭着眼睛都能默写”的程度。它太常考了不只是 AcWing 上有面试题里也经常拿它当前置题目。我的一个小技巧是如果想偷懒不写虚拟头结点可以在合并前先比较两个链表第一个节点的值把结果头结点先确定下来这样循环里就不用每轮判断空链了。但兜兜转转用下来最后还是觉得dummy方式最省心。每当遇到更复杂的链表操作时我都会先想这个问题能不能用一个虚拟头结点把“第一个节点”的特判消灭掉这个方法帮我解决了不少看起来很难的题目。