刷AcWing题库走到链表这一块的时候第3639题“链表合并”绝对值得你停下来认真写一遍。我在拿到这道题的时候第一反应是“这不就是归并两个有序数组换了个壳子嘛”但真动手写发现指针操作里藏了不少细节。合并两个有序单链表可以说是链表题的“九九乘法表”——后面无论是归并排序、合并K个链表还是求两个有序链表集合的差集最后都会落到这个动作上。这道题的标准描述不复杂给你两个按非递减顺序排列的单链表把它们合并成一个新的有序链表并返回。按评测时常见的输入格式来理解第一行是两个链表的长度n和m第二行是链表A的n个元素值第三行是链表B的m个元素值输出合并后的完整序列。道理一听就懂但真正动手写的时候有人栽在怎么优雅处理头结点有人栽在静态链表建链顺序搞反还有人栽在空链表这种极端用例上。这篇文章我不打算只贴一段能过的代码而是把三种主流写法、背后的取舍逻辑、以及我在实际刷题中踩过的坑都翻出来讲透。不管你是刚学数据结构的新手还是准备面试想巩固链表基本功的选手这篇应该都能给你点东西。1. 先弄清题目到底要什么题意还原与三个隐藏考点1.1 输入输出形态与评测习惯先把题意固定在具体形态上后面所有代码才有讨论基础。按照刷题时的常规约定输入大概是这样的3 4 1 3 5 2 4 6 8第一行的3和4分别表示链表A有3个结点、链表B有4个结点第二行是A的所有元素值第三行是B的所有元素值。两个链表本身就是有序的这里注意题目措辞往往是“非递减”也就是说允许出现相等元素比如1 2 2 3完全合法。输出就一行把合并后的完整序列打出来元素之间用空格分隔像这样1 2 3 4 5 6 8如果你习惯用C的cin读取空格和换行都不用操心cin x会自动跳过空白。但有一点要养成习惯先判断输入是否可能有多组测试数据。有些题不会明说“多组数据”但评测数据里就是循环给到EOF为止。保险的做法是写成while (cin n m)或者按题目要求来。我见过不少人在单组数据上AC了换到多组数据版本就挂不是算法错是读入方式不对。1.2 三个真正想考你的点这道题表面上是“把两个链表接在一起”实际上考了三层东西。第一层是归并逻辑。两个有序序列合并成一个有序序列用双指针从头往后扫哪个小就取哪个这是归并排序的核心操作也是这道题的主干思路。第二层是链表指针操作。数组里归并只要管下标链表里归并要管的是next指针。前者是“把值搬过去”后者是“把结点串起来”。很多数组写得很熟的人一换到链表就手足无措本质上是不习惯“结点”这个抽象——每个结点既是数据又是通往下一个结点的线索。第三层是边界条件。空链表、其中一个链表已经走完、两个链表等长、两个链表所有元素全相等……这些场景都需要在几行代码里处理干净。说白了这道题是用来检验你“能不能在不需要别人帮忙调试的情况下独立写出没有逻辑漏洞的指针操作”。1.3 为什么说它是基础题里的试金石我看过很多人在刷LeetCode 21题合并两个有序链表的时候觉得“太简单了”直接背了个递归版本就过。但到AcWing这种需要自己处理完整输入输出、自己构建链表的题目上反而卡壳了。原因很简单平台帮你把链表构建好了你只需要写个合并函数而这里你需要从裸数据开始构建链表再合并再遍历输出。这多出来的几步恰恰是实际工程里最常遇到的情况——你不是在操作一个已经存在的链表而是要自己把散落的数据组织成链表结构。所以我一直觉得AcWing3639比单纯的“合并两个链表函数”更有价值它是一道完整链路的题建链、合并、遍历、输出每一步都是基本功。只要你能不查资料独立写完并跑通链表这块的地基就算打得差不多了。2. 迭代归并最符合直觉也最稳妥的合并实现2.1 归并思路到底从哪来我先讲最核心的迭代写法。思路一句话就能说清同时从两个链表的头结点出发比较当前结点的值谁小就把谁接到结果链表的尾部然后让那个链表的指针往后走一步。重复这个过程直到某一个链表走空最后把另一个链表剩下的部分整体接上去。这个思路本身在数组归并里已经被验证过无数遍关键是怎么在链表上落地。链表的“移动”不是i而是p p-next链表的“追加”不是c[k] a[i]而是tail-next p。2.2 哨兵结点为什么能省掉一半判断新手最容易纠结的问题是结果链表一开始是空的第一个结点到底怎么接如果不做任何处理你需要先判断head是不是空——是空就让head p不是空就让tail-next p。这个if放在循环里每轮都得判断烦不烦烦。于是就有了哨兵结点dummy node的经典技巧先在栈上创建一个不参与数据的结点让tail指向它后面所有结点都统一走tail-next p这一条路不需要特判头结点。循环结束后真正的头结点就是dummy.next。用生活类比的话哨兵结点相当于排队时站在第一个位置前面那个“维持秩序的人”他不在队伍里但有了他你永远不用考虑“现在队伍是空的怎么办”这个特殊情况。这对编码的简化是立竿见影的。2.3 完整的C参考实现#include iostream using namespace std; struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode dummy(0); // 哨兵结点栈上分配无需手动释放 ListNode* tail dummy; while (a b) { if (a-val b-val) { tail-next a; a a-next; } else { tail-next b; b b-next; } tail tail-next; } tail-next a ? a : b; return dummy.next; } int main() { int n, m; cin n m; ListNode* headA nullptr; ListNode* tailA nullptr; for (int i 0; i n; i) { int x; cin x; ListNode* node new ListNode(x); if (!headA) { headA node; tailA node; } else { tailA-next node; tailA node; } } ListNode* headB nullptr; ListNode* tailB nullptr; for (int i 0; i m; i) { int x; cin x; ListNode* node new ListNode(x); if (!headB) { headB node; tailB node; } else { tailB-next node; tailB node; } } ListNode* result mergeTwoLists(headA, headB); for (ListNode* p result; p; p p-next) { cout p-val ; } cout endl; return 0; }2.4 逐行精读每个细节都是为什么重点看mergeTwoLists函数其它部分其实是在搭场景。ListNode dummy(0);——哨兵结点的值给多少无所谓它永远不会被读取只是为了有一个确定的next位置。注意这里是在栈上创建的对象函数结束自动销毁不需要delete。如果你写成ListNode* dummy new ListNode(0);用完还得记得delete纯属给自己找麻烦。while (a b)——这个循环条件是“两个链表都还有结点”。一旦某一个走空了循环立刻退出。C里空指针是nullptr在布尔上下文里等价于false所以直接写a b是合法的也最简洁。a-val b-val——注意我用的是而不是。题目说两个链表都是非递减序列意味着可能存在相等值。用会把链表A中的相等元素先接出去这符合一般意义上的“稳定归并”。虽然大部分题目不校验稳定性但养成用的习惯没有坏处。tail tail-next;——这一步是新手容易忘的。你把tail-next指向了a但tail自己还停在原地如果不往后挪下一轮又会把新结点接到老位置直接把前面的链覆盖掉。每一步操作后都要问自己tail现在到底指向哪tail-next a ? a : b;——循环结束后最多有一个链表还没走完也可能两个都恰好走完此时三元表达式会接上nullptr。直接把剩余部分整个链过来不需要再一个一个遍历。这一步是O(1)的但如果你写成while(a) { ... } while(b) { ... }再逐个接也对只是没必要。3. 数组模拟链表更贴合AcWing平台的实用写法3.1 为什么用数组模拟刷过AcWing的人对“静态链表”应该不陌生。很多题解的代码里根本没有struct ListNode而是用两个数组e[]存结点值ne[]存下一个结点的下标。这种写法叫作“用数组模拟链表”在很多需要快速建链、频繁增删的场景下比new对象快得多也省去了指针管理的负担。我不止一次听到有人问为什么AcWing上那么多答案都在用数组模拟不用结构体原因主要有两个。一是评测环境对速度敏感new一个结点的开销虽然单次不大但数据量上来之后成千上万次分配累计耗时可观用e[]和ne[]就是普通数组读写快且稳定。二是数组模拟的“指针”就是整数下标排错的时候能直接打印下标逻辑特别清晰非常适合算法竞赛。3.2 e[] / ne[] 的语义约定如下e[i]下标为i的结点的值。ne[i]下标为i的结点的下一个结点下标如果是-1表示链表结束。用idx表示当前可用的下一个空闲下标每新建一个结点就e[idx] x然后idx。头结点本身就是一个整数下标。比如headA 0表示链表A的第一个结点存储在e[0]。遍历的时候长这样for (int i headA; i ! -1; i ne[i]) { cout e[i] ; }这和for (ListNode* p head; p; p p-next)是完全对应的。理解了这一层指针链表和数组链表在你眼里就是同一件事的两种书写方式。3.3 完整实现合并两个静态链表#include iostream using namespace std; const int N 100010; int e[N], ne[N]; int mergeList(int a, int b) { int dummy N - 1; // 使用一个不会参与数据的下标做哨兵 ne[dummy] -1; int tail dummy; while (a ! -1 b ! -1) { if (e[a] e[b]) { ne[tail] a; a ne[a]; } else { ne[tail] b; b ne[b]; } tail ne[tail]; } ne[tail] (a ! -1) ? a : b; return ne[dummy]; } int main() { int n, m; cin n m; int headA -1, tailA -1; int idx 0; for (int i 0; i n; i) { int x; cin x; e[idx] x; ne[idx] -1; if (headA -1) { headA idx; tailA idx; } else { ne[tailA] idx; tailA idx; } idx; } int headB -1, tailB -1; for (int i 0; i m; i) { int x; cin x; e[idx] x; ne[idx] -1; if (headB -1) { headB idx; tailB idx; } else { ne[tailB] idx; tailB idx; } idx; } int result mergeList(headA, headB); for (int i result; i ! -1; i ne[i]) { cout e[i] ; } cout endl; return 0; }注意我在mergeList里借用N - 1这个下标作为哨兵。使用前给ne[dummy] -1是必须的否则tail第一次取ne[tail]时读到的是未初始化值。如果你觉得借用最后一个下标不够直观也可以单独定义一个dummy idx再把idx初始化成0之前先预留一个位置本质上都一样。还有一点值得强调数组链表合并和指针链表合并的操作是一一对应的。指针版写的是tail-next a; a a-next;数组版写的是ne[tail] a; a ne[a];。一旦你熟练了其中一种另一种就是机械翻译唯一的障碍是不习惯“下一个结点”这个概念从指针变成了下标。3.4 头插法与尾插法新手最容易踩的坑建链表有头插法和尾插法两种方式。头插法是每次把新结点插到链表头部代码短但会把输入序列逆序。比如输入1 3 5头插法建出来的链表是5 - 3 - 1。在这个题目里输入是已经拍好序的递增序列你头插法建出来直接变成递减合并逻辑全乱。我看到很多人在AcWing上问“为什么我输入1 3 5输出5 3 1”十有八九就是用了头插法。解决办法有两个一是改用尾插法就是上面代码里的做法维护一个tail指针/下标每次接到尾巴上二是坚持头插法但读完后把链表反转回来。我的建议是直接在读入环节用尾插法多维护一个变量避免再写一个反转函数少一个出错点。4. 递归合并与原地合并两种备选方案的取舍账本4.1 递归写法代码短但有代价递归版本在LeetCode上非常流行因为它简洁到让人一眼就能背下来ListNode* mergeTwoLists(ListNode* a, ListNode* b) { if (!a) return b; if (!b) return a; if (a-val b-val) { a-next mergeTwoLists(a-next, b); return a; } else { b-next mergeTwoLists(a, b-next); return b; } }这代码的优雅程度确实没话说逻辑就是a的头比较小那结果头就是a剩下要合并的是a-next和b反之亦然。递归的终止条件是某一方为空直接返回另一方。但你必须清楚它的代价每次递归调用都要占用一层系统栈。两个链表各有n和m个结点时递归深度可能达到n m。如果你的合并函数在真实工程里要处理百万级结点这种写法在极端情况下可能直接把栈压爆。算法竞赛里结点数通常在10^5以内一般没事但面试时如果你只写递归版本面试官很可能会追问一句“这个递归深度是多少你愿意在生产环境里用它吗”你要是答不上来印象分会打折扣。我的态度是递归版本可以用来理解归并的“分治”本质也可以作为面试时的优雅答案之一但最终手写代码我推荐迭代版因为它的空间复杂度是严格的O(1)且没有任何栈溢出的风险。4.2 原地合并一个容易被误解的概念有人一听“原地合并”以为是要在某个链表内部挪动结点写起来特别复杂。其实链表场景下的“原地”概念没那么玄乎——你只需要修改next指针不需要申请任何新结点那就是原地操作。上面第2节的迭代写法本质上就已经是原地合并了。什么情况下你会产生“需要新链表”的错觉可能是因为数组归并里你必须开一个临时数组来存结果因为数组的元素搬不动。但链表不一样结点的物理位置不需要动你只是把一个个结点从两条链上摘下来再串到一条新链上。整个过程没有创建新结点只有指针被改写。所以严格来说迭代归并本身就是空间O(1)的原地算法不需要额外造轮子。如果你非要写一个不依赖哨兵结点的版本代码是下面这个形态ListNode* mergeTwoLists(ListNode* a, ListNode* b) { if (!a) return b; if (!b) return a; ListNode* head; if (a-val b-val) { head a; a a-next; } else { head b; b b-next; } ListNode* tail head; while (a b) { if (a-val b-val) { tail-next a; a a-next; } else { tail-next b; b b-next; } tail tail-next; } tail-next a ? a : b; return head; }对比第2节带哨兵的版本你会发现多了一段“处理第一个结点”的特判。这就是哨兵的价值所在——它不是功能必需品而是让代码更均匀、更少分支的手段。两种都能AC我个人倾向带哨兵。4.3 三种方案怎么选场景化决策方案代码量时间复杂度额外空间风险点推荐场景迭代哨兵中等O(nm)O(1)几乎没有笔试、工程、教学递归最短O(nm)O(nm)栈空间深度过大可能栈溢出面试展示思路、链表不长时无哨兵迭代中等O(nm)O(1)首结点特判容易写错想挑战自己时可以练练如果你时间只够掌握一种那不用犹豫就练第2节的迭代哨兵版本。它既好写又安全而且很容易改造成合并K个有序链表的两两合并版。5. 空链表与全相等边界条件实测与评测陷阱5.1 四种你必须反复验证的输入形态很多代码能过常规用例但挂在边界上。我列一下我在实际评测和本地自测时一定会构造的测试用例。第一种是空链表。输入0 0两个链表都为空。迭代合并里while (a b)不会进入tail-next a ? a : b接上nullptr输出为空行。这个用例能帮你确认哨兵初值和输出逻辑不会空指针崩溃。第二种是一个为空另一个非空。比如0 3加一行1 2 3。此时合并函数直接返回非空的那条链要保证没有任何额外的越界操作。如果你的代码在进入合并前先解引用了空指针这里就会炸。第三种是一个链表的所有元素都小于另一个。比如A是1 2 3B是4 5 6。这种情况下循环会一直从A取元素直到A走完再把B整体接上去。这个过程能检验“剩余链表整体接上”的逻辑是否正确。第四种是两个链表全相等。比如A是1 1 1B也是1 1 1。这里用和用的输出会不一样但都是有序的。我建议用因为题目如果将来加了“保持原链表相对顺序”的隐藏要求用就会错。5.2 数组大小、多组数据、输入格式的坑如果你用数组模拟链表数组开多大需要心里有数。总共有nm个结点极端情况下所有元素都进一条链表所以e[]和ne[]至少要能容纳n m个元素。题目没给范围时我习惯开100010然后假设单组数据里n m不会超过这个数。如果你不确定可以写成动态增长的vectorint e, nepush_back时下标天然连续完全没问题。多组数据的陷阱也值得单独说。有些题目输入长这样3 4 1 3 5 2 4 6 8 2 2 1 7 2 9这表示有两组测试数据。你的数组模拟代码在第二组数据开始时需要重置headA headB -1但idx可以继续累加不用清零。不清零的原因是新结点存在新的下标位置旧空间留着不碍事清零反而可能在遍历时误入旧链表。如果使用指针动态分配版本则每组数据结束后最好把旧链表释放掉虽然评测环境不强求但习惯要养好。还有一个隐蔽的坑输入数据可能跨行。比如第一组链表A的数据占了不止一行或者行尾有多余空格。这些都被cin x自动处理了不需要你操心。如果你用的是scanf格式字符串写%d同样能跳过空白。千万不要去手动处理换行那是自找麻烦。5.3 内存管理算法题之外的真实工程问题在AcWing上写完就交new出来的结点不释放评测系统会自动回收进程内存这没任何问题。但如果你把这段代码搬到实际工程里每一轮合并都产生新链表不释放旧结点就是内存泄漏。我在教别人写链表时会建议他们在本地测试时写一个deleteList函数遍历一遍把结点全部delete掉。不是为了评测是为了养成意识。更工程一点的做法是用std::unique_ptr管理结点这样链表析构时自动递归释放。但要注意unique_ptr的析构会一路递归下去超长链表析构时也可能栈溢出这又是另一个话题了。哪怕只是做题关注内存管理也能帮你少踩指针的坑。C里最常见的段错误往往不是逻辑错而是指针指飞了——比如你提前把某个结点的next改了之后又用旧指针去访问它就会读到已经被改写的数据。试着在关键位置cout一下当前的a、b下标或指针地址是最直接的排错手段。6. 从链表合并延伸到逆序、差集、带环链表题族通吃打法6.1 逆序、插入基础操作如何组合出高阶题链表合并练熟之后我强烈建议趁着手感还在把另外几个基础操作一起过一遍。第一个是单链表逆序用迭代三指针prev、cur、next或者递归都行。逆序和合并经常组合出题比如“在不新建链表的情况下将两个非递减链表合并后逆序输出”——解法路径是先合并再逆序或者先逆序再合并殊途同归。第二个是链表插入。给定一个有序链表和一个新值把它插到正确位置。这个操作的循环条件通常是while (p-next p-next-val x)注意这里用的是一前一后两个指针。它和合并操作的“选小头接入”在本质上是对称的练完合并再练插入你对“尾插”和“中间插”的区别会理解得特别深。第三个是基于链表的两个集合差集。如果两个集合用有序链表表示求A - B的过程其实就是一边比较一边跳过相同元素。核心循环里三个值两两比较A当前值小于B当前值时A的当前值就是差集一员相等时两边都跳过A当前值大于B当前值时B往后走。这完全就是合并逻辑的一个变体你会觉得特别眼熟。6.2 合并K个有序链表熟悉的动作升级版面试里比合并两个链表更高频的是“合并K个有序链表”。最朴素的思路是依次两两合并第一次合并链表1和2结果再和3合并……时间复杂度是O(K * N)K是链表数量N是每个链表的平均长度。这种做法好理解但数据量大起来性能堪忧。更好的方案是用最小堆优先队列。把K个头结点塞进堆里每次弹出最小的那个接进结果链然后把它的下一个结点重新入堆。时间复杂度降到O(N * logK)。这里你会再次看见链表合并的核心——每次从多个候选中挑最小的。所以不要觉得3639太基础就不重视它就是你解K路归并的那把钥匙。6.3 带环链表与循环单链表和合并题的关系热词里出现了“循环单链表”和“单链表的基本操作实验”说明很多人是在实验课上碰到这块。循环单链表和普通链表的差异只在尾结点的next指向头结点而不是nullptr。合并两个循环链表时不能直接用上面的while (a b)因为链表没有天然终点你需要额外记录起始位置或者预先断开环。这提醒我们一件事很多链表题不是算法难而是数据结构形态没搞清。写遍历之前先问自己这个链表的终点是nullptr还是头结点如果是循环链表无限循环的bug会让你头疼半天。每道题动手前花十秒把链表的形态和终止条件写下来能省下大量调试时间。6.4 我的个人实操心得最后分享几个我自己刷链表题攒下来的习惯。第一先手写小测试用例再跑代码。我会在纸上画三个结点的链表手动走一遍合并过程看指针每一步指向哪。不要嫌幼稚指针题画图比空想可靠一百倍。我见过太多人代码写完了跑样例不过结果一画图立刻发现是tail忘了后移。第二本地测试时打印链表结构。比如写一个printList(ListNode* head)每次操作后都看一眼当前链表长什么样。对于数组模拟链表就打印下标序列i ne[i]。这样一旦出错你能立刻定位是哪一步把链给搞断了。第三把代码“翻着写”一遍。如果你习惯写指针版本试着把同样逻辑用数组模拟写一遍如果你只会数组模拟试着用struct重写一次。两种形态互相翻译会让你的理解从“背代码”升级到“懂结构”。我在准备面试的时候就用这种方法练习效果非常明显很多东西是在“翻译”的过程中突然想通的。第四注意命名。别用a、b、p、q全堆一起建议用headA、headB、tail、cur这类有语义的名字。链表操作本来就绕命名再模糊写完三天后回看自己都认不出。代码是写给人看的其次才是让机器跑。这道题刷完我做了一件我一直推荐别人做的事把所有链表基础题归成一个“题族”写在同一篇笔记里包括单链表逆序、有序链表插入、合并两个有序链表、求两个有序链表集合差集、链表环路检测。合并是里面第一个解决的题目而其它几个题的核心循环回头看都长得很像。所谓刷题手感很多时候就是从这种“发现不同题长得很像”的时刻积累出来的。
刷AcWing题库走到链表这一块的时候第3639题“链表合并”绝对值得你停下来认真写一遍。我在拿到这道题的时候第一反应是“这不就是归并两个有序数组换了个壳子嘛”但真动手写发现指针操作里藏了不少细节。合并两个有序单链表可以说是链表题的“九九乘法表”——后面无论是归并排序、合并K个链表还是求两个有序链表集合的差集最后都会落到这个动作上。这道题的标准描述不复杂给你两个按非递减顺序排列的单链表把它们合并成一个新的有序链表并返回。按评测时常见的输入格式来理解第一行是两个链表的长度n和m第二行是链表A的n个元素值第三行是链表B的m个元素值输出合并后的完整序列。道理一听就懂但真正动手写的时候有人栽在怎么优雅处理头结点有人栽在静态链表建链顺序搞反还有人栽在空链表这种极端用例上。这篇文章我不打算只贴一段能过的代码而是把三种主流写法、背后的取舍逻辑、以及我在实际刷题中踩过的坑都翻出来讲透。不管你是刚学数据结构的新手还是准备面试想巩固链表基本功的选手这篇应该都能给你点东西。1. 先弄清题目到底要什么题意还原与三个隐藏考点1.1 输入输出形态与评测习惯先把题意固定在具体形态上后面所有代码才有讨论基础。按照刷题时的常规约定输入大概是这样的3 4 1 3 5 2 4 6 8第一行的3和4分别表示链表A有3个结点、链表B有4个结点第二行是A的所有元素值第三行是B的所有元素值。两个链表本身就是有序的这里注意题目措辞往往是“非递减”也就是说允许出现相等元素比如1 2 2 3完全合法。输出就一行把合并后的完整序列打出来元素之间用空格分隔像这样1 2 3 4 5 6 8如果你习惯用C的cin读取空格和换行都不用操心cin x会自动跳过空白。但有一点要养成习惯先判断输入是否可能有多组测试数据。有些题不会明说“多组数据”但评测数据里就是循环给到EOF为止。保险的做法是写成while (cin n m)或者按题目要求来。我见过不少人在单组数据上AC了换到多组数据版本就挂不是算法错是读入方式不对。1.2 三个真正想考你的点这道题表面上是“把两个链表接在一起”实际上考了三层东西。第一层是归并逻辑。两个有序序列合并成一个有序序列用双指针从头往后扫哪个小就取哪个这是归并排序的核心操作也是这道题的主干思路。第二层是链表指针操作。数组里归并只要管下标链表里归并要管的是next指针。前者是“把值搬过去”后者是“把结点串起来”。很多数组写得很熟的人一换到链表就手足无措本质上是不习惯“结点”这个抽象——每个结点既是数据又是通往下一个结点的线索。第三层是边界条件。空链表、其中一个链表已经走完、两个链表等长、两个链表所有元素全相等……这些场景都需要在几行代码里处理干净。说白了这道题是用来检验你“能不能在不需要别人帮忙调试的情况下独立写出没有逻辑漏洞的指针操作”。1.3 为什么说它是基础题里的试金石我看过很多人在刷LeetCode 21题合并两个有序链表的时候觉得“太简单了”直接背了个递归版本就过。但到AcWing这种需要自己处理完整输入输出、自己构建链表的题目上反而卡壳了。原因很简单平台帮你把链表构建好了你只需要写个合并函数而这里你需要从裸数据开始构建链表再合并再遍历输出。这多出来的几步恰恰是实际工程里最常遇到的情况——你不是在操作一个已经存在的链表而是要自己把散落的数据组织成链表结构。所以我一直觉得AcWing3639比单纯的“合并两个链表函数”更有价值它是一道完整链路的题建链、合并、遍历、输出每一步都是基本功。只要你能不查资料独立写完并跑通链表这块的地基就算打得差不多了。2. 迭代归并最符合直觉也最稳妥的合并实现2.1 归并思路到底从哪来我先讲最核心的迭代写法。思路一句话就能说清同时从两个链表的头结点出发比较当前结点的值谁小就把谁接到结果链表的尾部然后让那个链表的指针往后走一步。重复这个过程直到某一个链表走空最后把另一个链表剩下的部分整体接上去。这个思路本身在数组归并里已经被验证过无数遍关键是怎么在链表上落地。链表的“移动”不是i而是p p-next链表的“追加”不是c[k] a[i]而是tail-next p。2.2 哨兵结点为什么能省掉一半判断新手最容易纠结的问题是结果链表一开始是空的第一个结点到底怎么接如果不做任何处理你需要先判断head是不是空——是空就让head p不是空就让tail-next p。这个if放在循环里每轮都得判断烦不烦烦。于是就有了哨兵结点dummy node的经典技巧先在栈上创建一个不参与数据的结点让tail指向它后面所有结点都统一走tail-next p这一条路不需要特判头结点。循环结束后真正的头结点就是dummy.next。用生活类比的话哨兵结点相当于排队时站在第一个位置前面那个“维持秩序的人”他不在队伍里但有了他你永远不用考虑“现在队伍是空的怎么办”这个特殊情况。这对编码的简化是立竿见影的。2.3 完整的C参考实现#include iostream using namespace std; struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode dummy(0); // 哨兵结点栈上分配无需手动释放 ListNode* tail dummy; while (a b) { if (a-val b-val) { tail-next a; a a-next; } else { tail-next b; b b-next; } tail tail-next; } tail-next a ? a : b; return dummy.next; } int main() { int n, m; cin n m; ListNode* headA nullptr; ListNode* tailA nullptr; for (int i 0; i n; i) { int x; cin x; ListNode* node new ListNode(x); if (!headA) { headA node; tailA node; } else { tailA-next node; tailA node; } } ListNode* headB nullptr; ListNode* tailB nullptr; for (int i 0; i m; i) { int x; cin x; ListNode* node new ListNode(x); if (!headB) { headB node; tailB node; } else { tailB-next node; tailB node; } } ListNode* result mergeTwoLists(headA, headB); for (ListNode* p result; p; p p-next) { cout p-val ; } cout endl; return 0; }2.4 逐行精读每个细节都是为什么重点看mergeTwoLists函数其它部分其实是在搭场景。ListNode dummy(0);——哨兵结点的值给多少无所谓它永远不会被读取只是为了有一个确定的next位置。注意这里是在栈上创建的对象函数结束自动销毁不需要delete。如果你写成ListNode* dummy new ListNode(0);用完还得记得delete纯属给自己找麻烦。while (a b)——这个循环条件是“两个链表都还有结点”。一旦某一个走空了循环立刻退出。C里空指针是nullptr在布尔上下文里等价于false所以直接写a b是合法的也最简洁。a-val b-val——注意我用的是而不是。题目说两个链表都是非递减序列意味着可能存在相等值。用会把链表A中的相等元素先接出去这符合一般意义上的“稳定归并”。虽然大部分题目不校验稳定性但养成用的习惯没有坏处。tail tail-next;——这一步是新手容易忘的。你把tail-next指向了a但tail自己还停在原地如果不往后挪下一轮又会把新结点接到老位置直接把前面的链覆盖掉。每一步操作后都要问自己tail现在到底指向哪tail-next a ? a : b;——循环结束后最多有一个链表还没走完也可能两个都恰好走完此时三元表达式会接上nullptr。直接把剩余部分整个链过来不需要再一个一个遍历。这一步是O(1)的但如果你写成while(a) { ... } while(b) { ... }再逐个接也对只是没必要。3. 数组模拟链表更贴合AcWing平台的实用写法3.1 为什么用数组模拟刷过AcWing的人对“静态链表”应该不陌生。很多题解的代码里根本没有struct ListNode而是用两个数组e[]存结点值ne[]存下一个结点的下标。这种写法叫作“用数组模拟链表”在很多需要快速建链、频繁增删的场景下比new对象快得多也省去了指针管理的负担。我不止一次听到有人问为什么AcWing上那么多答案都在用数组模拟不用结构体原因主要有两个。一是评测环境对速度敏感new一个结点的开销虽然单次不大但数据量上来之后成千上万次分配累计耗时可观用e[]和ne[]就是普通数组读写快且稳定。二是数组模拟的“指针”就是整数下标排错的时候能直接打印下标逻辑特别清晰非常适合算法竞赛。3.2 e[] / ne[] 的语义约定如下e[i]下标为i的结点的值。ne[i]下标为i的结点的下一个结点下标如果是-1表示链表结束。用idx表示当前可用的下一个空闲下标每新建一个结点就e[idx] x然后idx。头结点本身就是一个整数下标。比如headA 0表示链表A的第一个结点存储在e[0]。遍历的时候长这样for (int i headA; i ! -1; i ne[i]) { cout e[i] ; }这和for (ListNode* p head; p; p p-next)是完全对应的。理解了这一层指针链表和数组链表在你眼里就是同一件事的两种书写方式。3.3 完整实现合并两个静态链表#include iostream using namespace std; const int N 100010; int e[N], ne[N]; int mergeList(int a, int b) { int dummy N - 1; // 使用一个不会参与数据的下标做哨兵 ne[dummy] -1; int tail dummy; while (a ! -1 b ! -1) { if (e[a] e[b]) { ne[tail] a; a ne[a]; } else { ne[tail] b; b ne[b]; } tail ne[tail]; } ne[tail] (a ! -1) ? a : b; return ne[dummy]; } int main() { int n, m; cin n m; int headA -1, tailA -1; int idx 0; for (int i 0; i n; i) { int x; cin x; e[idx] x; ne[idx] -1; if (headA -1) { headA idx; tailA idx; } else { ne[tailA] idx; tailA idx; } idx; } int headB -1, tailB -1; for (int i 0; i m; i) { int x; cin x; e[idx] x; ne[idx] -1; if (headB -1) { headB idx; tailB idx; } else { ne[tailB] idx; tailB idx; } idx; } int result mergeList(headA, headB); for (int i result; i ! -1; i ne[i]) { cout e[i] ; } cout endl; return 0; }注意我在mergeList里借用N - 1这个下标作为哨兵。使用前给ne[dummy] -1是必须的否则tail第一次取ne[tail]时读到的是未初始化值。如果你觉得借用最后一个下标不够直观也可以单独定义一个dummy idx再把idx初始化成0之前先预留一个位置本质上都一样。还有一点值得强调数组链表合并和指针链表合并的操作是一一对应的。指针版写的是tail-next a; a a-next;数组版写的是ne[tail] a; a ne[a];。一旦你熟练了其中一种另一种就是机械翻译唯一的障碍是不习惯“下一个结点”这个概念从指针变成了下标。3.4 头插法与尾插法新手最容易踩的坑建链表有头插法和尾插法两种方式。头插法是每次把新结点插到链表头部代码短但会把输入序列逆序。比如输入1 3 5头插法建出来的链表是5 - 3 - 1。在这个题目里输入是已经拍好序的递增序列你头插法建出来直接变成递减合并逻辑全乱。我看到很多人在AcWing上问“为什么我输入1 3 5输出5 3 1”十有八九就是用了头插法。解决办法有两个一是改用尾插法就是上面代码里的做法维护一个tail指针/下标每次接到尾巴上二是坚持头插法但读完后把链表反转回来。我的建议是直接在读入环节用尾插法多维护一个变量避免再写一个反转函数少一个出错点。4. 递归合并与原地合并两种备选方案的取舍账本4.1 递归写法代码短但有代价递归版本在LeetCode上非常流行因为它简洁到让人一眼就能背下来ListNode* mergeTwoLists(ListNode* a, ListNode* b) { if (!a) return b; if (!b) return a; if (a-val b-val) { a-next mergeTwoLists(a-next, b); return a; } else { b-next mergeTwoLists(a, b-next); return b; } }这代码的优雅程度确实没话说逻辑就是a的头比较小那结果头就是a剩下要合并的是a-next和b反之亦然。递归的终止条件是某一方为空直接返回另一方。但你必须清楚它的代价每次递归调用都要占用一层系统栈。两个链表各有n和m个结点时递归深度可能达到n m。如果你的合并函数在真实工程里要处理百万级结点这种写法在极端情况下可能直接把栈压爆。算法竞赛里结点数通常在10^5以内一般没事但面试时如果你只写递归版本面试官很可能会追问一句“这个递归深度是多少你愿意在生产环境里用它吗”你要是答不上来印象分会打折扣。我的态度是递归版本可以用来理解归并的“分治”本质也可以作为面试时的优雅答案之一但最终手写代码我推荐迭代版因为它的空间复杂度是严格的O(1)且没有任何栈溢出的风险。4.2 原地合并一个容易被误解的概念有人一听“原地合并”以为是要在某个链表内部挪动结点写起来特别复杂。其实链表场景下的“原地”概念没那么玄乎——你只需要修改next指针不需要申请任何新结点那就是原地操作。上面第2节的迭代写法本质上就已经是原地合并了。什么情况下你会产生“需要新链表”的错觉可能是因为数组归并里你必须开一个临时数组来存结果因为数组的元素搬不动。但链表不一样结点的物理位置不需要动你只是把一个个结点从两条链上摘下来再串到一条新链上。整个过程没有创建新结点只有指针被改写。所以严格来说迭代归并本身就是空间O(1)的原地算法不需要额外造轮子。如果你非要写一个不依赖哨兵结点的版本代码是下面这个形态ListNode* mergeTwoLists(ListNode* a, ListNode* b) { if (!a) return b; if (!b) return a; ListNode* head; if (a-val b-val) { head a; a a-next; } else { head b; b b-next; } ListNode* tail head; while (a b) { if (a-val b-val) { tail-next a; a a-next; } else { tail-next b; b b-next; } tail tail-next; } tail-next a ? a : b; return head; }对比第2节带哨兵的版本你会发现多了一段“处理第一个结点”的特判。这就是哨兵的价值所在——它不是功能必需品而是让代码更均匀、更少分支的手段。两种都能AC我个人倾向带哨兵。4.3 三种方案怎么选场景化决策方案代码量时间复杂度额外空间风险点推荐场景迭代哨兵中等O(nm)O(1)几乎没有笔试、工程、教学递归最短O(nm)O(nm)栈空间深度过大可能栈溢出面试展示思路、链表不长时无哨兵迭代中等O(nm)O(1)首结点特判容易写错想挑战自己时可以练练如果你时间只够掌握一种那不用犹豫就练第2节的迭代哨兵版本。它既好写又安全而且很容易改造成合并K个有序链表的两两合并版。5. 空链表与全相等边界条件实测与评测陷阱5.1 四种你必须反复验证的输入形态很多代码能过常规用例但挂在边界上。我列一下我在实际评测和本地自测时一定会构造的测试用例。第一种是空链表。输入0 0两个链表都为空。迭代合并里while (a b)不会进入tail-next a ? a : b接上nullptr输出为空行。这个用例能帮你确认哨兵初值和输出逻辑不会空指针崩溃。第二种是一个为空另一个非空。比如0 3加一行1 2 3。此时合并函数直接返回非空的那条链要保证没有任何额外的越界操作。如果你的代码在进入合并前先解引用了空指针这里就会炸。第三种是一个链表的所有元素都小于另一个。比如A是1 2 3B是4 5 6。这种情况下循环会一直从A取元素直到A走完再把B整体接上去。这个过程能检验“剩余链表整体接上”的逻辑是否正确。第四种是两个链表全相等。比如A是1 1 1B也是1 1 1。这里用和用的输出会不一样但都是有序的。我建议用因为题目如果将来加了“保持原链表相对顺序”的隐藏要求用就会错。5.2 数组大小、多组数据、输入格式的坑如果你用数组模拟链表数组开多大需要心里有数。总共有nm个结点极端情况下所有元素都进一条链表所以e[]和ne[]至少要能容纳n m个元素。题目没给范围时我习惯开100010然后假设单组数据里n m不会超过这个数。如果你不确定可以写成动态增长的vectorint e, nepush_back时下标天然连续完全没问题。多组数据的陷阱也值得单独说。有些题目输入长这样3 4 1 3 5 2 4 6 8 2 2 1 7 2 9这表示有两组测试数据。你的数组模拟代码在第二组数据开始时需要重置headA headB -1但idx可以继续累加不用清零。不清零的原因是新结点存在新的下标位置旧空间留着不碍事清零反而可能在遍历时误入旧链表。如果使用指针动态分配版本则每组数据结束后最好把旧链表释放掉虽然评测环境不强求但习惯要养好。还有一个隐蔽的坑输入数据可能跨行。比如第一组链表A的数据占了不止一行或者行尾有多余空格。这些都被cin x自动处理了不需要你操心。如果你用的是scanf格式字符串写%d同样能跳过空白。千万不要去手动处理换行那是自找麻烦。5.3 内存管理算法题之外的真实工程问题在AcWing上写完就交new出来的结点不释放评测系统会自动回收进程内存这没任何问题。但如果你把这段代码搬到实际工程里每一轮合并都产生新链表不释放旧结点就是内存泄漏。我在教别人写链表时会建议他们在本地测试时写一个deleteList函数遍历一遍把结点全部delete掉。不是为了评测是为了养成意识。更工程一点的做法是用std::unique_ptr管理结点这样链表析构时自动递归释放。但要注意unique_ptr的析构会一路递归下去超长链表析构时也可能栈溢出这又是另一个话题了。哪怕只是做题关注内存管理也能帮你少踩指针的坑。C里最常见的段错误往往不是逻辑错而是指针指飞了——比如你提前把某个结点的next改了之后又用旧指针去访问它就会读到已经被改写的数据。试着在关键位置cout一下当前的a、b下标或指针地址是最直接的排错手段。6. 从链表合并延伸到逆序、差集、带环链表题族通吃打法6.1 逆序、插入基础操作如何组合出高阶题链表合并练熟之后我强烈建议趁着手感还在把另外几个基础操作一起过一遍。第一个是单链表逆序用迭代三指针prev、cur、next或者递归都行。逆序和合并经常组合出题比如“在不新建链表的情况下将两个非递减链表合并后逆序输出”——解法路径是先合并再逆序或者先逆序再合并殊途同归。第二个是链表插入。给定一个有序链表和一个新值把它插到正确位置。这个操作的循环条件通常是while (p-next p-next-val x)注意这里用的是一前一后两个指针。它和合并操作的“选小头接入”在本质上是对称的练完合并再练插入你对“尾插”和“中间插”的区别会理解得特别深。第三个是基于链表的两个集合差集。如果两个集合用有序链表表示求A - B的过程其实就是一边比较一边跳过相同元素。核心循环里三个值两两比较A当前值小于B当前值时A的当前值就是差集一员相等时两边都跳过A当前值大于B当前值时B往后走。这完全就是合并逻辑的一个变体你会觉得特别眼熟。6.2 合并K个有序链表熟悉的动作升级版面试里比合并两个链表更高频的是“合并K个有序链表”。最朴素的思路是依次两两合并第一次合并链表1和2结果再和3合并……时间复杂度是O(K * N)K是链表数量N是每个链表的平均长度。这种做法好理解但数据量大起来性能堪忧。更好的方案是用最小堆优先队列。把K个头结点塞进堆里每次弹出最小的那个接进结果链然后把它的下一个结点重新入堆。时间复杂度降到O(N * logK)。这里你会再次看见链表合并的核心——每次从多个候选中挑最小的。所以不要觉得3639太基础就不重视它就是你解K路归并的那把钥匙。6.3 带环链表与循环单链表和合并题的关系热词里出现了“循环单链表”和“单链表的基本操作实验”说明很多人是在实验课上碰到这块。循环单链表和普通链表的差异只在尾结点的next指向头结点而不是nullptr。合并两个循环链表时不能直接用上面的while (a b)因为链表没有天然终点你需要额外记录起始位置或者预先断开环。这提醒我们一件事很多链表题不是算法难而是数据结构形态没搞清。写遍历之前先问自己这个链表的终点是nullptr还是头结点如果是循环链表无限循环的bug会让你头疼半天。每道题动手前花十秒把链表的形态和终止条件写下来能省下大量调试时间。6.4 我的个人实操心得最后分享几个我自己刷链表题攒下来的习惯。第一先手写小测试用例再跑代码。我会在纸上画三个结点的链表手动走一遍合并过程看指针每一步指向哪。不要嫌幼稚指针题画图比空想可靠一百倍。我见过太多人代码写完了跑样例不过结果一画图立刻发现是tail忘了后移。第二本地测试时打印链表结构。比如写一个printList(ListNode* head)每次操作后都看一眼当前链表长什么样。对于数组模拟链表就打印下标序列i ne[i]。这样一旦出错你能立刻定位是哪一步把链给搞断了。第三把代码“翻着写”一遍。如果你习惯写指针版本试着把同样逻辑用数组模拟写一遍如果你只会数组模拟试着用struct重写一次。两种形态互相翻译会让你的理解从“背代码”升级到“懂结构”。我在准备面试的时候就用这种方法练习效果非常明显很多东西是在“翻译”的过程中突然想通的。第四注意命名。别用a、b、p、q全堆一起建议用headA、headB、tail、cur这类有语义的名字。链表操作本来就绕命名再模糊写完三天后回看自己都认不出。代码是写给人看的其次才是让机器跑。这道题刷完我做了一件我一直推荐别人做的事把所有链表基础题归成一个“题族”写在同一篇笔记里包括单链表逆序、有序链表插入、合并两个有序链表、求两个有序链表集合差集、链表环路检测。合并是里面第一个解决的题目而其它几个题的核心循环回头看都长得很像。所谓刷题手感很多时候就是从这种“发现不同题长得很像”的时刻积累出来的。
