深拷贝与链表排序：LeetCode Hot 100 经典题的指针操作全解析

先声明一下：这两道题我在刷 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 的节点，先串好 next，random 先不管。但问题来了——你复制第一个节点时，它的 random 指向第三个节点，而第三个节点的拷贝可能还没创建。哪怕你有原链表的指针，也不能直接把这个原指针赋给新节点的 random，否则就破坏了深拷贝的语义。

所以核心问题变成：如何建立“原链表节点 -> 新链表节点”的映射。只要能查到这个映射，组装 random 就只是查表操作。

2.2 哈希表解法：最直观的查表思路

既然要建立映射，最直接的数据结构就是哈希表。第一次遍历原链表，为每个原节点创建新节点，并把“原节点指针 -> 新节点指针”的对应关系存进 unordered_map。第二次遍历原链表，根据映射关系把新节点的 next 和 random 都补上。

class Solution { public: Node* copyRandomList(Node* head) { if (!head) return nullptr; unordered_map<Node*, 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)，只用了几个临时指针。

两种解法的对比如下：

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 << ", random=null"; 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 到合并结果的末尾。

如果剩余部分不足 size，right 会变成 nullptr，merge(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 时需要特判，否则 len=1 时外层 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 个升序链表，都会顺手很多。