有序链表合并算法详解：从双指针到虚拟头结点

前两天在 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 为空就直接返回 l2，l2 为空就返回 l1，两个都为空就返回空。用虚拟头结点的写法，这些情况其实已经被统一处理了：while直接不进，tail->next = l1 ? l1 : l2会把非空的那个链整体接上。但如果你是手写不带虚拟头结点的版本，必须一开始就处理空指针，否则后面l1->val或l2->val会直接解引用空指针。

第二个是相等值。在比较时，我习惯用<=而不是<。用<=时，如果两个链表有相同值的节点，会优先取 l1 的节点，这种合并是“稳定”的。用<时，相同值会优先取 l2 的节点，结果仍然有序，但节点的来源顺序和稳定合并不同。面试时如果面试官追问“如果两个值相等，应该怎么处理？”至少你要能说出“结果有序性不受影响，但稳定性有区别”。

第三个是单个节点的极端情况。比如 l1 只有一个 1，l2 只有一个 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 -> A3，l2 是 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结束，循环链表这样写就死循环了。合并两个循环链表时，我习惯按三步走：

1. 先把两个循环链表在头结点处“断开”，让尾节点的next置为nullptr，把它们变成两条普通的单链表。
2. 按普通单链表的合并逻辑处理，得到一条普通链表。
3. 遍历合并后的链表找到尾节点，把尾节点的next指向新的头节点，重新形成循环。

这三步里最容易踩的坑是第一步。断环必须记住原来的头是谁，否则断完之后你以为拿到了头，实际可能已经走到别的位置去了。另外要注意长度只有 1 的循环链表，断开操作要格外小心，避免自己打断自己的唯一链接。

有人问“为什么不直接在环上合并？”理论上也可以，但指针操作更复杂，容易出现遗漏。先把循环转成普通链，是降低犯错成本的做法。在竞赛或机试中，如果题目没有特别要求必须原地在环上操作，断环再合并通常更稳妥。

4.3 常见进阶：合并 K 个有序链表

如果把两个链表合并扩展到 K 条有序链表，就是更常见的“合并 K 个有序链表”问题。这个题也是很多大厂面试的常客。

处理 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方式最省心。每当遇到更复杂的链表操作时，我都会先想这个问题：能不能用一个虚拟头结点，把“第一个节点”的特判消灭掉？这个方法帮我解决了不少看起来很难的题目。