“合并两个有序链表”这道题，出现在面试题单里的频率高得有点离谱，但真要让你用 C 实现一份能直接编译、跑通、不漏内存、边界还不出错的代码，能一次写成的人其实没想象中多。我做链表相关的练习和工程代码有些年头了，从最早课程里的单链表基本操作实验，到后来处理日志流合并、批量数据归并，两个有序链表的归并逻辑反复出现——它本身就是归并排序的底层动作，也是多路数据流合并的最小单元。
链表这种结构的特点是节点散落在堆内存里，靠指针一根一根串起来。遍历、插入、删除全靠指针操作，指针接错一步就是断链、丢节点，或者干脆跑成死循环，而且因为它不像数组那样能一眼看到全部内容，调试时你不打印出来根本不知道中间状态长什么样。这篇文章就把这道题彻底拆开：三种 C 实现的思路分别长什么样、为什么这么写、各自在什么场景下更合适，再加上我实际写代码时踩过的坑和一套能复用的调试方法。不管你是刚学完单链表基本操作实验的学生，还是想把链表基本功重新夯一遍的开发者，这里的内容都能直接抄走，代码能编译、能跑、能验证。
1. 先把题目和地基理清楚
1.1 节点结构体：一行 typedef 里的门道
一切从节点开始。C 语言里写链表节点，标准写法是这样：
typedef struct ListNode { int val; struct ListNode *next; } ListNode;这里有个特别容易让初学 C 的人卡住的点：struct ListNode *next;里面必须写struct，不能偷懒写成ListNode *next;。因为在结构体定义还没结束的时候，ListNode这个别名还没生效，编译器不认识它。这是 C 和 C++ 的一个明显差异——如果你写的是struct ListNode { int val; ListNode *next; };，在 C++ 里能过，在 C 里直接报错。很多人从 C++ 的写法切回 C 时会在这里栽一跤，明明逻辑没问题，编译就是不过。
至于val的类型，题目里一般是int。但真实工程里我会多想一想：如果后面要合并的是字符串、时间戳或者结构体负载，这个字段就得换。为了迁移方便，可以在练习阶段就用typedef int ElemType;把元素类型抽出来，将来换类型只改一行。这是个小习惯，但能省掉后面大面积的查找替换。
另外一定要记住：链表节点一般是用malloc从堆上申请的。堆内存不会自动回收，用完必须手动free。这一点在后面三种思路的对比里会反复出现，因为不同思路对“谁负责释放内存”这件事的要求完全不同。
1.2 三种思路的分水岭到底在哪
很多人做完这道题就以为自己会了，但被追问“还有别的写法吗”就答不上来。其实这道题的所有解法都落在两个维度的组合上：
第一个维度是节点是否复用。你可以在归并过程中为每个结果节点新申请一块内存，把原链表当成只读的输入源；也可以直接修改原节点的next指针，把两个链表“穿针引线”地缝成一条，全程不申请任何新节点。这两种做法的代码结构差别非常大，内存责任也完全不同。
第二个维度是迭代还是递归。迭代是用循环加指针变量推进，递归则是把“合并剩下的部分”当成一个子问题交给函数自己处理。
把这两个维度交叉一下，能得到四种组合。我这里选三种最有代表性的讲：新建节点尾插法（迭代 + 不复用）、哨兵节点双指针迭代法（迭代 + 复用，这是工程里最常用的）、递归法（递归 + 复用）。每种我都会给完整代码、逐段解释，以及它独有的坑。
1.3 一份能反复用的测试脚手架
写链表题最忌讳的就是“光写核心函数不写测试”。链表的结果没法像数组那样直接printf("%d", arr)看全，你必须准备几个辅助函数，不然出了问题两眼一抹黑。下面这份脚手架我一直在用，后面三种思路都靠它验证：
#include <stdio.h> #include <stdlib.h> typedef struct ListNode { int val; struct ListNode *next; } ListNode; /* 创建单个节点 */ ListNode *createNode(int val) { ListNode *node = (ListNode *)malloc(sizeof(ListNode)); if (node == NULL) { fprintf(stderr, "malloc failed\n"); exit(EXIT_FAILURE); } node->val = val; node->next = NULL; return node; } /* 用数组构建链表，返回头指针 */ ListNode *buildList(const int *arr, int n) { ListNode dummy; dummy.next = NULL; ListNode *tail = &dummy; for (int i = 0; i < n; i++) { tail->next = createNode(arr[i]); tail = tail->next; } return dummy.next; } /* 打印整条链表 */ void printList(const char *tag, ListNode *head) { printf("%s: ", tag); while (head != NULL) { printf("%d -> ", head->val); head = head->next; } printf("NULL\n"); } /* 释放整条链表 */ void freeList(ListNode *head) { while (head != NULL) { ListNode *tmp = head->next; free(head); head = tmp; } }注意buildList里我也用了哨兵节点（栈上的dummy），这是为了让尾插逻辑统一，不用单独处理“第一个节点”这个特殊分支。这个小技巧后面还会详细讲，它正是思路二的核心。释放函数freeList里必须先存下head->next再free(head)，反过来写就是标准的 use-after-free，Valgrind 一跑就报错。
测试的时候我会用几组数据：等长的、长度悬殊的、全是重复值的、以及有负数或极大值的。这几组基本能覆盖掉绝大多数指针错误。
2. 思路一：新建节点尾插法，最直白但最费内存
2.1 逻辑拆解：为什么新手第一反应都是这个
这个思路的心智模型最简单：我拿两个游标分别扫两条链表，每次比较当前两个节点的值，谁小就把谁的值“抄”到一个新节点里，接到结果链表的尾巴上，然后让那个游标往前走一步。哪条先走完，就把另一条剩下的值继续抄成新节点接上去。
它之所以是新手的第一反应，因为它完全不涉及“修改原链表的指针”这件事。原链表从头到尾保持原样，你只是在读它。对于刚学链表、对指针操作还没把握的人来说，这种“只读不写”的做法心理负担最小。而且在某些真实约束下这个特性反而是刚需：比如原链表是别人传给你的只读数据，或者两条链表在别处还有别的引用，你不能把它们拆了重组。这时候新建节点就是唯一正确的选择。
代价也很直接。假设两条链表长度分别是 m 和 n，结果长度是 m+n，你就要额外申请 m+n 个节点。空间复杂度从 O(1) 涨到了 O(m+n)。更要命的是，原来的 2(m+n) 份内存（两条链表本身）还在，最后你还得把这堆一起释放掉，否则就是实打实的内存泄漏。
2.2 完整实现与逐行说明
ListNode *mergeTwoLists_new(ListNode *l1, ListNode *l2) { ListNode *head = NULL, *tail = NULL; while (l1 != NULL && l2 != NULL) { int v; if (l1->val <= l2->val) { v = l1->val; l1 = l1->next; } else { v = l2->val; l2 = l2->next; } ListNode *node = (ListNode *)malloc(sizeof(ListNode)); if (node == NULL) return head; /* 简化处理，实际应释放已分配部分 */ node->val = v; node->next = NULL; if (head == NULL) { head = node; tail = node; } else { tail->next = node; tail = node; } } /* 把剩余的那条链表继续抄完 */ ListNode *rest = (l1 != NULL) ? l1 : l2; while (rest != NULL) { ListNode *node = (ListNode *)malloc(sizeof(ListNode)); if (node == NULL) return head; node->val = rest->val; node->next = NULL; tail->next = node; tail = node; rest = rest->next; } return head; }这里有个可以优化的细节：剩余部分的malloc失败处理。我为了代码清爽写成了直接返回，工程里更稳妥的做法是先把已分配的结果链表整条释放掉再返回错误码，避免“半条结果链表”泄漏。这就是用新建节点法必须要多操心的东西——每一处malloc都得配一条对应的失败路径。
另外注意比较用的是<=而不是<。这不是随便写的。当两个节点值相等时，取l1的在前，能让结果里等值元素的先后次序和原链表保持一致。这个性质在归并排序里非常关键，因为归并排序想保持数据原有的相对次序，完全依赖归并这一步的这个符号。写成<的话，排序就变成了不保持次序的版本，输出结果虽然还是有序的，但等值元素的顺序可能被打乱。
2.3 为什么必须用尾指针，而不是每次从头找尾
有人图省事会这么写：每次要接新节点时，从head开始循环走到最后一个节点，再挂上去。这个写法的复杂度是 O(n²)——结果链表每长一个节点，你就要多走一遍。链表长度到几千，性能差距就非常明显了。
正确做法是维护一个tail指针，永远指向结果链表的最后一个节点。插入时tail->next = node; tail = node;两步搞定，O(1)。这里有个小陷阱：tail = node千万别忘了写。忘了写的话，tail一直指着旧尾巴，下次再挂节点就会把上一次挂的那个节点覆盖掉，最终结果链表长度永远停在两个节点上，而且你还得花很久才能看出问题在哪。
2.4 内存账要算清：两份内存都得释放
用这个思路时，最后要释放的不只是结果链表，还有输入的两条原链表。因为归并过程中你没有修改它们，它们始终是完整的两条链。测试代码应该长这样：
int a[] = {1, 3, 5, 7}; int b[] = {2, 4, 6, 8}; ListNode *la = buildList(a, 4); ListNode *lb = buildList(b, 4); ListNode *res = mergeTwoLists_new(la, lb); printList("merged", res); freeList(res); /* 结果链表 */ freeList(la); /* 原链表，别忘了 */ freeList(lb);漏掉后两行，就是 2(m+n) 个节点的泄漏。我在早期项目里就因为这个习惯不好，在循环里反复调用归并函数，内存用量一路涨到被系统杀掉进程，查了半天才发现是归并函数没改动原链表、调用方以为它改了，于是两边都没释放。
注意：新建节点法最大的隐患不是逻辑错，而是内存责任不清。写的时候就要在注释里明确写清“输入链表由调用方负责释放”，否则换个人接手代码必然踩坑。
3. 思路二：哨兵节点加双指针迭代，工程里的首选
3.1 哨兵节点到底解决了什么问题
如果不用哨兵节点，复用原节点的写法会变成这样：
ListNode *head = NULL, *tail = NULL; while (l1 && l2) { if (l1->val <= l2->val) { if (head == NULL) { head = l1; tail = l1; } else { tail->next = l1; tail = l1; } l1 = l1->next; } /* l2 分支同理 */ }每个分支里都塞了一个head == NULL的判断，因为“接第一个节点”和“接后续节点”的代码不一样：前者要同时更新head和tail，后者只更新tail。这意味着每个分支都得写两遍，代码立刻膨胀，出错概率也跟着涨。最容易犯的错就是某个分支忘了更新head，结果函数返回 NULL，明明合并完成了却什么都拿不到。
哨兵节点（也叫哑结点、虚拟头结点）就是解决这个问题的。它的做法是：先造一个临时的、不存有效数据的节点，把它当成结果链表的“第零个节点”。所有真实节点都往它后面挂。这样一来，“接第一个节点”和“接后续节点”的代码就完全一样了，都不需要判断head是不是空。循环结束后，真正的头结点就是dummy.next。
这个技巧的价值在于它消除了代码里的“特殊情况”，让主循环变成纯粹的重复动作。凡是链表题里出现“需要单独处理头结点”的场景，基本都可以用哨兵节点干掉那个分支。
3.2 完整实现与指针走向推演
ListNode *mergeTwoLists_iter(ListNode *l1, ListNode *l2) { ListNode dummy; /* 栈上的哨兵节点 */ dummy.next = NULL; 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; }我拿l1 = [1,3,5]、l2 = [2,4]走一遍，方便你建立指针直觉：
| 步骤 | l1 当前 | l2 当前 | 挂上去的节点 | 结果链表 | tail 指向 |
|---|---|---|---|---|---|
| 初始 | 1 | 2 | - | dummy | dummy |
| 1 | 3 | 2 | 1 | 1 | 1 |
| 2 | 3 | 4 | 2 | 1→2 | 2 |
| 3 | 5 | 4 | 3 | 1→2→3 | 3 |
| 4 | 5 | NULL | 4 | 1→2→3→4 | 4 |
| 收尾 | 5 | - | 整条 5 | 1→2→3→4→5 | - |
关键就在第 4 步之后：l2变成 NULL，循环退出，此时tail还指着节点 4，把整条剩余的l1直接挂在tail->next上就完了。这一步不需要循环，因为链表的“剩余部分”本身已经是一条有序链，指针一挂就全部接上，这是链表相对数组的一个天然便利。
注意这里面有个微妙的指针顺序：必须先把l1 = l1->next存下来，再挂tail->next。如果写成tail->next = l1; tail = tail->next; l1 = l1->next;，逻辑上其实也对，但更绕；而如果写成tail->next = l1; l1 = l1->next; tail = tail->next;，就可能出问题——因为tail刚被赋成l1，接着l1前进后，tail->next指向的仍然是正确的后继，实际上还是对的，但可读性差。我推荐固定用“挂指针、前移游标、更新尾指针”这个顺序，形成肌肉记忆。
3.3 返回 dummy.next 而不是 &dummy
这是初学者最常见的错误，而且症状很迷惑：函数返回后你拿到一个指针，打印它的val得到一堆垃圾数据，或者程序直接崩。
原因很简单：dummy是栈上的局部变量。函数一返回，它所在的那块栈帧就被回收了，&dummy是一个悬空指针。而dummy.next指向的是你从原链表上“偷”来的堆节点，那些节点的生命周期不受函数栈帧影响，所以合法。
我见过有人为了“保险”，把哨兵节点也写成malloc出来的。这其实是可以的，但那就多了一次申请和释放，还得记得free掉这个临时节点，反而把 O(1) 空间这个优点打折扣了。用栈变量就行，只要记住只返回dummy.next。
3.4 链表调试的三个土办法
链表不能像数组那样直接用打印看全，所以我自己的调试工具箱里有三招，用起来非常顺：
第一招是上面写的printList，每次合并完立刻打一遍，确认长度和顺序。别小看这一步，很多“少了一个节点”或者“顺序错了”的问题，打印出来一眼就能定位。
第二招是快慢指针查环。如果结果打印不完、程序卡死，八成是有环。用 Floyd 判环法三行代码就能确认：
ListNode *slow = head, *fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) { printf("cycle detected\n"); break; } }第三招是打印节点地址。把printf("%d(%p) -> ", head->val, (void *)head);写进打印函数，如果同一条链表里出现了两个相同的地址，那必然是有节点被重复挂接了。这个办法在处理 K 路合并时特别有效。
注意：调试链表时不要只看最终结果。每一步的
tail指向哪、l1和l2走到哪了，都要心里有数。我习惯在纸上画出三个指针的位置，走两步对一次，比盯着屏幕强。
4. 思路三：递归实现，代码最短但要想清代价
4.1 递推式是怎么推出来的
递归写链表题的核心思路是：不要想整条链表怎么合并，只想清楚第一步该干什么，然后把剩下的活交给函数自己。
第一步永远是比较l1->val和l2->val：
- 如果
l1更小（或相等），那么结果链表的头一定是l1这个节点，接下来只要把l1->next和l2这两条链合并后的结果，接在l1后面。 - 反过来，如果
l2更小，结果头就是l2，接下来合并l1和l2->next，接在l2后面。
终止条件也很清楚：任意一条链为空，剩下的那条就是结果，直接返回。
这就是完整的递归定义，代码短得惊人。
4.2 完整实现与调用栈展开
ListNode *mergeTwoLists_rec(ListNode *l1, ListNode *l2) { if (l1 == NULL) return l2; if (l2 == NULL) return l1; if (l1->val <= l2->val) { l1->next = mergeTwoLists_rec(l1->next, l2); return l1; } else { l2->next = mergeTwoLists_rec(l1, l2->next); return l2; } }拿l1 = [1,3]、l2 = [2]展开一下调用过程，你就能明白它是怎么工作的：
merge([1,3], [2]) → 1 < 2，所以 l1->next = merge([3], [2]) → 3 > 2，所以 l2->next = merge([3], NULL) → l2 为空，返回 [3] → 返回 [2,3] → 返回 [1,2,3]注意递归返回时执行的那句l1->next = ...是关键。它是自底向上做的：最后一层最先算完，把结果一层层往回接。这也是递推法容易写错的地方——很多人只写了return l1;却忘了先给l1->next赋值，结果返回的节点后面跟的还是原来的老链路，整条结果链就断了。
还有一个细节：if (l1 == NULL) return l2;这两句必须放在最前面。它们既是终止条件，也是递归能正确收尾的保证。顺序不能反，也不能漏掉l2 == NULL那一句，否则两条链同时为空时会解引用空指针。
4.3 递归的真实代价：栈深度不是开玩笑的
递归版本的代码只有 8 行，可读性也好，但它有一个容易被忽略的硬伤：调用栈深度等于结果链表的长度。
每合并一个节点就压一层栈帧，假设两条链表各长 5 万（这在日志处理里很常见），那就是 10 万层递归。普通进程的栈空间一般是 8MB 左右，一个栈帧按几十字节算，10 万层很可能直接把栈撑爆，程序收到段错误直接挂掉，而且崩溃现场往往看不出和链表有关。
所以我在实际项目里有一条自己的判断标准：
| 链表规模 | 推荐写法 | 理由 |
|---|---|---|
| 万级以内 | 递归可以接受 | 代码短，出错概率低 |
| 十万级以上 | 必须用迭代 | 栈深度是硬约束 |
| 输入规模不可控 | 必须用迭代 | 不能赌调用方传进来多长 |
另外还有一个常被误解的点：C 语言的标准里没有强制要求编译器做尾递归优化，而且这个递归本身就不是尾递归——递归调用返回后还要执行l1->next = ...和return l1，所以编译器没法把它优化成循环。指望编译器帮你消栈是不现实的。
4.4 递归写错的两个典型症状
我见过最多的两种错法，症状完全不同，但根因都是对“返回值要接住”这件事理解不透。
第一种是忘了赋值，写成这样：
if (l1->val <= l2->val) { mergeTwoLists_rec(l1->next, l2); /* 返回值丢了 */ return l1; }症状是：函数能返回，但结果链表只剩两个节点左右，后面的全丢了。因为递归虽然算出来了，但没人把它接到l1->next上，算完的那部分直接被丢弃。
第二种是接错了对象，比如写成l1->next = mergeTwoLists_rec(l1, l2->next);，参数传错，症状是要么无限递归、要么漏节点。
排查这两种错，最快的办法是在函数入口加一句打印：
printf("enter: l1=%d, l2=%d\n", l1 ? l1->val : -1, l2 ? l2->val : -1);看递归的进入顺序和退出顺序，一下子就清楚哪一层接错了。这一招看起来笨，但比单步调试快得多。
5. 三种思路横向对比与选型
5.1 一张表把差异说透
| 对比维度 | 思路一 新建节点 | 思路二 哨兵迭代 | 思路三 递归 |
|---|---|---|---|
| 时间复杂度 | O(m+n) | O(m+n) | O(m+n) |
| 额外空间 | O(m+n)，全是新节点 | O(1)，只有几个指针 | O(m+n)，栈帧 |
| 是否修改原链表 | 否，原链保持完整 | 是，节点被重新串联 | 是，同左 |
| 代码行数 | 约 30 行 | 约 15 行 | 约 8 行 |
| 主要风险 | 忘记释放输入链表 | 误返回&dummy | 长链表爆栈 |
| 适用场景 | 原数据只读、需保留原链 | 通用场景、面试首选 | 短链、追求代码简洁 |
这张表里最值得琢磨的是“是否修改原链表”这一行。它不是性能问题，而是接口契约问题。如果你写的函数会修改输入，必须在函数名或注释里明确表达出来，比如叫mergeInPlace。否则调用方拿着两条链表的其他引用继续用，就会拿到一堆已经被改得面目全非的数据。
5.2 面试里怎么说才显得真想清楚了
如果面试官只让你写一种，我建议直接写思路二，写完主动补一段话：“这里用了栈上的哨兵节点消除头结点特判，空间是 O(1)，不新申请内存。如果输入链表不允许被修改，我会改成新建节点的版本，代价是空间涨到 O(m+n)。递归版本代码最短，但栈深度等于链表长度，长链表下不适用。”
这段话能一次性展示三件事：你懂哨兵节点这个技巧、你清楚三种方案的空间差异、你知道怎么根据约束做取舍。比闷头写完一句不解释强得多。很多时候面试的胜负不在代码本身，而在你能不能把方案选择的理由说清楚。
5.3 用 Valgrind 把内存问题钉死
新建节点版本最容易留下的问题是泄漏，而且不看工具基本发现不了。我的做法是写完立刻跑一遍内存检查：
gcc -g -Wall -Wextra -o merge merge.c valgrind --leak-check=full --show-leak-kinds=all ./merge重点看输出里的三行：definitely lost、indirectly lost、still reachable。前两个只要不是 0，就说明有节点没被free。still reachable一般是你程序退出时还挂着的全局或栈上指针，不算严格泄漏，但我会顺手清干净。
用迭代法时，因为节点是从原链表“偷”来的，最终结果链表其实同时“包含”了两条原链表的所有节点。这时候你只需要freeList(result)一次就够了，再去释放la和lb就是双重释放，程序会直接 abort。这个细节我在第一次切到迭代法时就搞错过，把原来的测试代码一起保留，结果就是崩溃。
6. 常见问题与排查技巧实录
6.1 错误速查表
| 症状 | 最可能的原因 | 定位方法 |
|---|---|---|
| 返回 NULL，但合并明明做了 | 没用哨兵，某分支漏更新 head | 检查所有分支是否都写了head = ... |
| 结果链表只有两三个节点 | tail = tail->next漏写，尾指针没前移 | 打印每步的 tail 指向 |
| 程序打印到一半卡死 | 结果链表里形成了环 | 快慢指针判环 |
| 返回值全是垃圾数据 | 返回了&dummy而不是dummy.next | 看 return 语句 |
| 返回后 val 变大数 | 返回了已归还的栈地址 | 同上 |
| 双重释放崩溃 | 迭代法结果链覆盖了原链，还去释放原链 | 删掉多余的freeList |
| 尾递归版本段错误 | 链表太长，递归爆栈 | 改成迭代 |
| 等值元素顺序被打乱 | 比较用了<而不是<= | 检查比较符号 |
6.2 断链、丢节点、死循环的定位套路
这三类故障占了链表 bug 的绝大部分，我有一套固定的排查顺序。
先查断链。表现是结果打印出来比预期短，或者中间某个节点后面变成 NULL。做法是在主循环里每合并一步就打印一次当前结果链表。如果发现某一步之后链表突然短了，问题就在那一步的指针操作上，通常是tail->next和游标更新的顺序写错了。
再查丢节点。表现是总数不对，少了几个。做法是合并前后分别统计两条输入链表的节点数和结果链表的节点数，理论上应该满足count(result) == count(l1) + count(l2)。这个计数我会写成小函数，几行代码，但它能立刻告诉你“是不是真的少了”，而不是靠肉眼数。
最后查死循环。表现是打印停不下来，或者程序无响应。直接用快慢指针判环，确认有环之后再回去看哪一步被重复指向了。常见的成因是收尾那一步写成了tail->next = tail;之类的笔误，或者循环条件里用了永远为真的表达式。
6.3 边界场景清单，写完先自己过一遍
这道题的边界其实不多，但每一个都能让代码崩掉，所以我会照着一张清单逐项验证：
- 两条都是空链表，结果应该是空。
- 一条空、一条非空，结果应该是非空那条原样返回（注意迭代法在这个场景下不能改动它）。
- 两条都只有一个节点，验证最基本的分支。
- 等长但值全部相同，验证
<=带来的相对次序保持。 - 长度悬殊，比如一条 1 个节点、一条 1000 个节点，验证收尾拼接是不是整条接上。
- 包含负数，验证比较逻辑没写死成正数假设。
- 全部逆序和全部顺序，验证循环推进方向没问题。
这七条我一般在main里写成七个小测试，每个都打印输入和输出。写一次能用很久，后面改成 K 路合并还能继续复用。
提示：如果你在写迭代版本时觉得“应该没问题”，但还是不放心，加一句
assert(count(result) == m + n);。断言是链表调试里被严重低估的工具，几秒钟就能加上，能省下几十分钟的排查。
7. 举一反三：从两路归并到 K 路合并
7.1 分治法合并 K 条有序链表
两路合并写熟之后，自然就会遇到“K 条链表怎么合”的问题。最朴素的做法是拿第一条依次和后面每一条合并，这样做的时间复杂度是 O(K²N)，K 一大就不行了。更好的做法是分治：把 K 条链表两两配对合并，一轮之后剩下 K/2 条，再两两合并，直到剩一条。因为每一轮处理的总节点数都是 N，而轮数是 log K，所以总复杂度是 O(N log K)。
ListNode *mergeKLists(ListNode **lists, int k) { if (k == 0) return NULL; while (k > 1) { int j = 0; for (int i = 0; i < k; i += 2) { if (i + 1 < k) { lists[j++] = mergeTwoLists_iter(lists[i], lists[i + 1]); } else { lists[j++] = lists[i]; } } k = j; } return lists[0]; }这段代码直接复用了前面写的迭代合并函数，非常划算。要注意的是它会把lists数组原地改掉，调用方如果还要用原数组，得先拷贝一份。我第一次写的时候就没注意，结果外层还在遍历这个数组做别的统计，数据全乱了。
7.2 用最小堆替代两两合并
另一个思路是维护一个大小为 K 的最小堆，堆里存每条链表当前的头节点，每次弹出最小的那个接到结果后面，然后把它所属链表的下一个节点压回堆里。复杂度是 O(N log K)，和分治一样，但它的好处是可以处理流式输入：如果每条链表的数据是源源不断产生的，你不需要等所有数据都到齐，弹一个补一个就行。
C 语言里没有现成的堆，得自己写sift_up和sift_down，代码量会大不少。但如果你在做实时日志合并这类场景，这个方案是值得的，因为分治法必须先拿到全部 K 条链表的头，而堆可以随着数据到达动态调整。
7.3 这个逻辑在真实工程里的影子
我在实际项目里遇到过好几次这个逻辑的变体，列出来给你找找感觉。
一是归并排序的合并步骤。归并排序对数组的两半分别排好序之后，最后一步做的就是合并两个有序序列，只不过数组版本用的是下标比较加临时数组，链表版本用的就是本文这套指针操作。而且链表版本的归并排序有个额外好处：合并时不需要额外申请数组空间，只要改指针就行，这也是它在某些内存敏感场景里被选用的原因。
二是多路日志流合并。不同服务产生的日志各自按时间戳有序，要合成一条全局时间线，本质上就是 K 路合并，而且要求等值元素保持原有的先后次序。这时候用的就是带堆的方案，配合<=保证次序不乱。
三是增量数据对账。两个数据源各自按主键排好序，要找出差异，也是双指针齐头并进，谁小谁前进，遇到相等就配对。合并有序链表的那套指针移动逻辑在这里一模一样。
这也说明一个事：链表的基本操作——遍历、插入、删除、逆序——本身都不难，难的是把它们组合起来解决实际问题。合并两个有序链表恰好是这种组合里最小的一个单元，把它写扎实，后面这些扩展才有立足点。
我个人在这道题上折腾最久的一次，不是算法本身，而是内存责任。当时我为了图方便，一会儿用新建节点版、一会儿用迭代版，测试代码却只有一套，结果在迭代版上对结果链表和输入链表各释放了一次，程序在某个特定数据组合下才崩。后来我养成了一个习惯：每个函数开头写一行注释，明确写清“本函数是否修改输入、谁负责释放”，三种版本各配一套独立的测试用例，共用同一份打印和释放工具函数。这个习惯之后，即使再写更复杂的链表题，也很少再被内存问题绊住。
另外分享一个小技巧：写完之后别急着提交，把两条输入链表反转一下再跑一次（比如把[1,3,5]改成[5,3,1]），如果程序行为出现明显异常，说明你的代码对输入做了不该有的顺序假设。这一步我几乎每次都做，拦下过好几次隐藏的逻辑错误。
