先声明一下这两道题我在刷 LeetCode Hot 100 的时候反复遇到后来在周赛、模拟面试里也经常能瞥见它们的影子。T138 随机链表的复制考的是你对“深拷贝”这件事的理解以及链表中“指针映射关系”怎么处理T148 排序链表则是把链表操作和排序算法结合起来相当考验基本功。这篇文章不打算只贴代码我会把每一步的推导、为什么这么写、哪些地方容易踩坑都拆开讲一遍。刷链表题的朋友尤其是刚开始冲 Hot 100 的建议把这两题放在一起练因为它们对指针操作、递归边界、dummy 节点的理解要求很一致。1. 两题一起刷的价值都在考察“指针操作与边界控制”1.1 解题本质从“数组思维”切换到“链表思维”很多人刷排序、复制这类题下意识会用数组的思路去想。数组有下标访问任意元素是 O(1)做拷贝、排序都很直观但链表是“顺着指针走”的结构你要访问第 k 个节点只能从头一个个走无法跳跃。T138 和 T148 恰好让你彻底告别这种思维惯性。T138 的难点不在“复制节点”而在 random 指针。原链表里某个节点的 random 指向第三个节点你在复制链表中也得让对应的新节点的 random 指向“新链表中的第三个节点”而不是原链表的节点。这个映射关系如果没处理好复制出来的就是“带有原链表指针的假深拷贝”。T148 的难点则在于数组排序时我们可以随机访问、可以开辅助数组但链表排序要求你用 O(n log n) 的时间复杂度和常数级额外空间这就不能用简单的插入排序也不能动不动就把链表转成 vector。你需要掌握“链表切分”和“有序链表合并”这两个基本功它们其实就是归并排序在链表上的体现。两道题放在一起本质都在训练同一件事操作链表时你要清楚每个指针现在指向谁、下一步该指向谁、操作完后会不会破坏原有结构。这些能力在链表类的 Hard 题里尤其重要。1.2 为什么这类题在 Hot 100 和周赛中频繁出现看近期的 LeetCode 周赛题目链表题虽然不会每场都压轴出现但经常作为基础考点藏在中等题里。比如合并有序链表、链表反转、环形链表检测这些技巧是很多中等题的“前置技能”。T138 是经典的“指针映射”题T148 是典型的“分治 指针操作”题它们能同时覆盖以下考点链表节点的创建与连接快慢指针、dummy 节点的使用递归与迭代的空间复杂度权衡深拷贝与浅拷贝的区别排序算法在非随机访问数据结构上的适配Hot 100 是很多人刷题的主线列表把这两题放在一起练性价比很高。官方题解里常见的哈希表法、原地穿插法、自顶向下归并、自底向上归并都是面试中值得掌握的常规解法。2. T138 随机链表的复制哈希表与原地穿插两种解法的完整推导2.1 题意拆解与初版思路为什么不能“边遍历边复制”题目给的节点结构是这样的class Node { public: int val; Node* next; Node* random; Node(int _val) { val _val; next nullptr; random nullptr; } };每个节点除了 next还有一个 random 指针指向链表中的任意一个节点也可能指向空。要求你构造一个全新的链表新链表中每个节点的 val、next、random 关系都与原链表一一对应但所有节点都是新创建的不能复用原节点。最容易想到的方法是遍历原链表每遇到一个节点就 new 一个同样 val 的节点先串好 nextrandom 先不管。但问题来了——你复制第一个节点时它的 random 指向第三个节点而第三个节点的拷贝可能还没创建。哪怕你有原链表的指针也不能直接把这个原指针赋给新节点的 random否则就破坏了深拷贝的语义。所以核心问题变成如何建立“原链表节点 - 新链表节点”的映射。只要能查到这个映射组装 random 就只是查表操作。2.2 哈希表解法最直观的查表思路既然要建立映射最直接的数据结构就是哈希表。第一次遍历原链表为每个原节点创建新节点并把“原节点指针 - 新节点指针”的对应关系存进 unordered_map。第二次遍历原链表根据映射关系把新节点的 next 和 random 都补上。class Solution { public: Node* copyRandomList(Node* head) { if (!head) return nullptr; unordered_mapNode*, Node* mp; Node* cur head; // 第一次遍历创建新节点建立映射 while (cur) { mp[cur] new Node(cur-val); cur cur-next; } // 第二次遍历组装 next 和 random cur head; while (cur) { mp[cur]-next mp[cur-next]; // 注意mp[nullptr] 返回 nullptr mp[cur]-random mp[cur-random]; // 同理 cur cur-next; } return mp[head]; } };写到 mp[cur-next] 时有些朋友会担心如果 cur-next 是 nullptr那么 unordered_map 的 operator[] 会不会插入一个无效键答案是nullptr 可以作为一个普通的指针键值存在map[nullptr] 会返回一个默认构造的 Node*也就是 nullptr。所以这句代码在 cur-next 为空时是安全的不会崩溃。不过为了可读性你也可以写成mp[cur]-next cur-next ? mp[cur-next] : nullptr;哈希表解法的时间复杂度是 O(n)空间复杂度也是 O(n)。这个解法的优点是逻辑非常清晰两次遍历代码不容易出错作为面试的开场答案完全够用。缺点是额外占用了 O(n) 的哈希表空间。如果面试官追问“能不能不用额外空间”那就需要引出原地穿插法。2.3 原地穿插解法把原链表当成“天然哈希表”原地穿插法的核心思路很巧妙我们不需要哈希表而是把复制出来的新节点直接插在原节点的后面。这样原链表变成了“原节点 - 新节点 - 原节点 - 新节点...”的交替结构。此时任意原节点的 next就是它对应的新节点任意新节点的 random就是原节点 random 指向的节点的 next。整个算法分三步走第一步在每个原节点后面插入一个值相同的新节点。Node* cur head; while (cur) { Node* copy new Node(cur-val); copy-next cur-next; cur-next copy; cur copy-next; }第二步给所有新节点设置 random。原链表中 cur-random 指向某个原节点那么新节点 cur-next 的 random 应该指向 cur-random-next。如果 cur-random 为空那么新节点的 random 也保持为空。cur head; while (cur) { if (cur-random) { cur-next-random cur-random-next; } cur cur-next-next; }第三步把交替链表拆成两个独立的链表一个是原链表一个是复制链表。这里要注意不仅要返回复制链表的头还要把原链表的 next 指针恢复原样。cur head; Node* dummy new Node(0); Node* tail dummy; while (cur cur-next) { tail-next cur-next; // 取走新节点 tail tail-next; cur-next cur-next-next; // 恢复原链表 next cur cur-next; } return dummy-next;我在写拆分这一步时犯过一个典型错误先执行 cur-next cur-next-next再取新节点。这样做的结果是新节点还没被接进复制链表就被原链表的恢复操作跳过了。正确的顺序应该是先保存新节点、让 tail 接到它再恢复原链表的 next最后让 cur 后移。第三步执行完之后原链表基本恢复了原状复制链表的头节点就是 dummy-next。为了更严谨可以在返回前把原链表最后一个节点的 next 置空不过循环结束条件 cur cur-next 已经保证了不会把空节点接进链表所以实践中问题不大。时间上仍然是 O(n)但额外空间降到了 O(1)只用了几个临时指针。两种解法的对比如下维度哈希表法原地穿插法时间复杂度O(n)O(n)额外空间O(n)O(1)代码复杂度简单直观需要理清三次遍历的指针关系风险点基本不会出错第三步拆分顺序容易搞反面试推荐度先讲这个作为进阶优化方案提出2.4 T138 的易错点与调试技巧第一random 指向空节点。很多解法在第二步判断 cur-random 是否为空这个判断不能省。第二原地法的第三步不能写成先断开再取节点。我记得第一次在 LeetCode 上跑原地法提交后报错最后打印链表才发现复制链表中间断了一截就是拆分顺序的问题。第三检查深拷贝是否成功不能只看 next。我建议本地写一个辅助函数同时打印每个节点的值和 random 指向的节点的值把原链表和复制链表都打印出来对比。例如void printList(Node* head) { Node* cur head; while (cur) { cout val cur-val; if (cur-random) cout , random cur-random-val; else cout , randomnull; cout endl; cur cur-next; } }这样能快速发现 random 指向了原链表的旧节点或 random 丢失的问题。3. T148 排序链表归并排序在链表上的正确实现3.1 题目约束与常用排序方案的取舍题目要求对链表排序并且进阶要求是 O(n log n) 时间复杂度、O(1) 额外空间。这里先排除掉一些不符合要求的方案插入排序时间复杂度 O(n^2)数据量大时会超时。把链表转成 vector 再排序时间复杂度可以做到 O(n log n)但额外空间是 O(n)不满足常数空间的进阶要求。快速排序数组快排依赖下标访问链表上实现要额外维护指针虽然可以做“链表快排”但平均性能和代码复杂度都不如归并排序稳定。所以主流方案是归并排序。链表天然适合归并因为归并的关键操作是“将两个有序链表合并成一个”而合并两个有序链表在链表结构中实现起来非常顺手不需要额外数组。唯一的问题是怎么把链表切成两半。这里有两种实现方式自顶向下递归和自底向上迭代。3.2 自顶向下归并排序递归 快慢指针找中点自顶向下的思路是分治三步找中点拆分 - 递归排序左右两半 - 合并两个有序链表。找中点用快慢指针快指针每次走两步慢指针每次走一步快指针走到尾时慢指针就在链表中点。这里有一个细节初始时可以让 fast head-next而不是 fast head。这样当链表长度为偶数时slow 会落在中间两个节点的左边那个方便将链表均匀切分。将链表从中间断开时先保存 slow-next 作为右半部分的头然后把 slow-next 置空让左半部分独立成链。class Solution { public: ListNode* sortList(ListNode* head) { if (!head || !head-next) return head; ListNode* slow head; ListNode* fast head-next; while (fast fast-next) { slow slow-next; fast fast-next-next; } ListNode* mid slow-next; slow-next nullptr; // 断开左右 ListNode* left sortList(head); ListNode* right sortList(mid); return merge(left, right); } private: ListNode* merge(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; } };merge 函数里用了一个栈上的 dummy 节点这是链表操作里常用的技巧可以省去单独处理头节点的分支判断。合并到最后把剩余的那一整段链表直接接在 tail 后面即可因为剩下的那段有序链表内部不需要再调整。自顶向下的空间复杂度是 O(log n)来自递归调用栈的深度符合题目的“进阶要求”其实有点争议。很多官方题解默认接受这个解法但严格的 O(1) 空间应该用自底向上。3.3 自底向上归并排序迭代实现真正的 O(1) 空间自底向上的思路是先统计链表长度 n然后从长度为 1 的块开始两两合并再变成 2、4、8直到整个链表有序。整个过程完全迭代不需要递归栈。实现中最重要的辅助函数是 cut。cut 负责从链表中切出前 n 个节点返回剩余部分的头节点同时把切出的部分与原链表断开。ListNode* cut(ListNode* head, int n) { if (!head) return nullptr; ListNode* p head; while (--n p) { p p-next; } if (!p) return nullptr; ListNode* nextPart p-next; p-next nullptr; // 断开 return nextPart; }注意 cut 的循环条件--n 表示已经把一个节点算进切出的块里所以实际移动 n-1 次。如果链表长度不足 n则 p 可能走到空节点此时返回 nullptr表示没有剩余部分了。主循环这样写class Solution { public: ListNode* sortList(ListNode* head) { if (!head || !head-next) return head; int len 0; ListNode* cur head; while (cur) { len; cur cur-next; } ListNode dummy(0); dummy.next head; for (int size 1; size len; size 1) { ListNode* prev dummy; cur dummy.next; while (cur) { ListNode* left cur; ListNode* right cut(left, size); cur cut(right, size); // 下一段 left prev-next merge(left, right); while (prev-next) prev prev-next; } } return dummy.next; } private: ListNode* cut(ListNode* head, int n) { if (!head) return nullptr; ListNode* p head; while (--n p) p p-next; if (!p) return nullptr; ListNode* nextPart p-next; p-next nullptr; return nextPart; } ListNode* merge(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; } };每一轮合并中cur 表示当前要处理块的起始位置。先切出 left长度 size再切出 right长度 size此时 cur 变成剩余链表的头也就是下一轮循环要处理的 left。合并 left 和 right 后接到 prev 后面然后更新 prev 到合并结果的末尾。如果剩余部分不足 sizeright 会变成 nullptrmerge(left, nullptr) 会直接把 left 整段返回cur cut(nullptr, size) 也会返回 nullptr内层循环结束。这种情况是安全的。自底向上的空间复杂度严格为 O(1)只有几个辅助指针在 LeetCode 上跑大数据量时表现稳定。相比自顶向下它的代码理解难度更高一些但面试如果能把这种解法讲出来是比较加分的。3.4 T148 常见失误与实测心得第一找中点时 fast 的初始位置。fast 从 head 出发在链表长度为偶数时slow 会落在中点偏后的位置切分出的两半长度可能差 1这不算严重问题。但如果写成 while(fast fast-next) 且 fast 初值为 head链表为 1-2-3-4 时slow 最终指向 3左半是 1-2-3右半是 4递归深度会略增加。用 fast head-next 可以让左半更均匀不容易出现递归过深的问题。第二自顶向下递归时忘记断开 slow-next。如果不把 slow-next 置空左右两半会共享一段链表递归时会出现重复合并甚至死循环。第三自底向上时每次内层循环结束后要仔细检查 prev 是否指向了合并链表最后一个节点。如果漏掉 while(prev-next) 这一步下一轮的合并结果会接错位置。我在实际测试中发现自底向上版本在链上节点数为 1 或 2 时需要特判否则 len1 时外层 for 循环直接不执行返回 dummy.next 也是正确的。所以 if (!head || !head-next) 的判空还是很有必要的。另外本地测试自底向上版本时我建议在 cut 函数里加一行打印看每次 cut 后返回的 nextPart 是否符合预期。调试链表问题最怕“整个链表变成环”打印每一步的 next 指向能及时发现。4. 链表类题目通用的调试方法与面试策略4.1 五个必查的“断链点”刷完这两题我总结了一套针对链表问题的自查清单。第一操作前是否保存了后继节点。原地法调整指针时如果先改 cur-next再想访问原来的 next就已经找不到了所以要么提前用临时变量保存要么严格设计执行顺序。第二边界节点是否处理。head 为空的判空递归 base case 里 !head || !head-next 的写法自底向上循环里 len 的统计这些都是最常见的出错点。第三是否形成环。两个有序链表合并时如果 tail-next 没有正确指向剩余部分或者切分时没把 slow-next 置空链表就会成环程序运行起来会死循环。第四是否修改了原链表且没有恢复。T138 的原地穿插法如果复制完不拆回原链表原链表结构就被破坏了这在实际工程里是不可接受的。第五dummy 节点是否正确。dummy.next 在返回前是否是复制链表的头指针合并排序中 dummy.next 每轮结束后是否保持为当前轮次排序后的链表头。这些细节直接影响答案正确性。4.2 本地测试用例怎么设计很多算法题在 LeetCode 上直接提交出错后只能靠反复调试。链表题不一样我强烈建议本地写一个工具函数集合数组转链表、打印链表、释放链表内存这几段代码写熟了刷所有链表题效率都会提升。T138 的测试用例至少要覆盖这些情况单节点且 random 指向自己、random 指向空、random 指向头节点、长链表随机指向。T148 的测试用例则要覆盖链表已经是升序、完全逆序、所有值相同、只有一个节点、两个节点。我自己常用随机函数生成一个长度为 10 的链表random 随机指向某个节点或空然后对比原链表和复制链表的打印结果。这比只提交 LeetCode 再看报错要高效得多。4.3 面试和周赛中的实战策略从热词里能看到 LeetCode 周赛 430、热门 100 题这些都是大家高频关注的内容。以我个人的经验面试碰到链表题的节奏应该是这样的先讲最容易想到的方案比如 T138 的哈希表法把思路说清楚代码写对这已经是合格线。如果面试官追问“能不能不用额外空间”再写原地穿插法。T148 同理先写自顶向下归并把分治思想讲明白再提自底向上版本展示你对空间复杂度的理解。面试时边写边讲比闷头写要加分。比如写 T148 的快慢指针时可以主动说“这里 fast 从 head-next 出发是为了让中点均匀切分”面试官会认为你是真的理解而不是背题。周赛里遇到链表题优先保证简单解法先跑通不要一上来就追求 O(1) 空间。周赛比拼的是通过速度和正确率自底向上归并的细节多万一写错浪费的时间远大于省下的那点空间开销。我个人刷这两题的体会是第一遍看题解以为自己懂了合上书自己写一遍各种指针问题全冒出来。所以你至少应该在三到五天后不看题解重新写一遍直到能保持 15 分钟内完成这两道题。链表题的套路并不多无非就是遍历、断开、连接、合并但每道题都会在这些基础操作上多绕一点弯。把 T138 和 T148 彻底啃下来后面碰到链表环形检测、K 个一组翻转链表、合并 K 个升序链表都会顺手很多。