企业官网建设流程全解析

刷链表题的人大多有个共同体验：链表题单看都不难，难的是那些“你以为会了、一写就错”的题。LeetCode Hot 100 里的第138题“随机链表的复制”和第148题“排序链表”，恰好就是两种典型体验：一个是复制链表时被 random 指针卡住，一个是在链表上做排序时发现数组那套排序思维全用不上。这两道题我自己都写错过多次，回过头看，真正卡住人的往往不是算法本身，而是对“手动改指针”这件事不够熟练。

这两题放在一起刷非常合适。T138 考的是深拷贝与映射关系，T148 考的是链表二分与归并，表面上看起来完全无关，但底层的通用能力高度重合：哨兵节点、快慢指针、拆分与重接链表、处理边界条件。这篇文章直接拆解这两道题的完整解法，包括我实际试过的两种写法、翻车的地方和面试时被追问的细节。

1. T138 随机链表的复制：真正的难点在“映射”，不在“遍历”

1.1 先把题目翻译成人话

题目给的是一个特殊的链表节点，除了常规的 next 指针之外，还有一个 random 指针，可以指向链表中任意一个节点，也可以指向 null。要求复制这个链表，返回一个全新的链表，并且新链表里每个节点的 next 和 random 都要对应到新链表里的节点，而不是原链表的节点。

这就是我们常说的“深拷贝”。如果只是普通链表，复制非常简单，遍历一遍，边遍历边 new 节点就完事了。但加上 random 之后，问题就变了：当你在遍历过程中创建一个新节点时，random 指向的节点可能还没被创建；就算已经创建了，你怎么知道它对应的是哪个新节点？

所以这个题的核心不是“怎么复制”，而是“怎么把旧节点与新节点的映射关系建立起来，并且用这个映射把 random 指针补全”。

我先定义节点结构，方便后面统一看代码：

class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } }

很多语言里这个题的节点构造都差不多，核心就是多了一个 random 字段。

1.2 哈希表方案：先建映射，再补指针

最容易理解、也最稳妥的方案就是用哈希表。思路非常直接：第一遍遍历原链表，每遇到一个节点，就创建一个对应的新节点，并把“旧节点 -> 新节点”的对应关系存进哈希表。第二遍再遍历原链表，这次所有新节点都已经创建好了，可以放心地补 next 和 random。

public Node copyRandomList(Node head) { if (head == null) { return null; } Map<Node, Node> map = new HashMap<>(); Node cur = head; // 第一轮：建立旧节点到新节点的映射 while (cur != null) { map.put(cur, new Node(cur.val)); cur = cur.next; } // 第二轮：补全 next 和 random cur = head; while (cur != null) { map.get(cur).next = map.get(cur.next); map.get(cur).random = map.get(cur.random); cur = cur.next; } return map.get(head); }

这里有个很多人第一次写会困惑的点：map.get(cur.next)在cur.next为 null 时会不会报错？

不会。这是 HashMap 的一个特性，它允许 null 作为键。map.get(null)返回的就是 null。所以当原节点的 next 或 random 本来就是 null 时，映射出来的也是 null，不需要额外判断。

这个解法的时间复杂度是 O(n)，空间复杂度是 O(n)，因为额外开了一张哈希表。哈希表方案最大的价值是思路简单，面试时先说这个方案能帮助你快速建立信心，后面再优化空间。

1.3 原地穿插法：把空间从 O(n) 压到 O(1)

如果面试官追问“能不能不用哈希表”，面试官期待的答案就是原地穿插法。这个技巧非常经典，核心思想是：在原链表的每个节点后面插入它的复制节点，这样新旧节点天然相邻，random 的对应关系可以直接通过“原节点的 random.next”拿到。

整个流程分成三轮：

第一轮，在每个原节点后面插入复制节点。原链表 1 -> 2 -> 3 会变成 1 -> 1' -> 2 -> 2' -> 3 -> 3'。

第二轮，设置复制节点的 random。复制节点的 random 就是原节点的 random 的下一个节点。也就是cur.next.random = cur.random.next。这里需要注意，只有当cur.random != null时才需要处理。

第三轮，拆分链表。把新节点依次从链表中抽出来，同时恢复原链表的 next 结构。

public Node copyRandomList(Node head) { if (head == null) { return null; } Node cur = head; // 第一轮：在每个原节点后面插入复制节点 while (cur != null) { Node copy = new Node(cur.val); copy.next = cur.next; cur.next = copy; cur = copy.next; } // 第二轮：设置复制节点的 random cur = head; while (cur != null) { if (cur.random != null) { cur.next.random = cur.random.next; } cur = cur.next.next; } // 第三轮：拆分链表 Node dummy = new Node(0); Node tail = dummy; cur = head; while (cur != null) { tail.next = cur.next; tail = tail.next; cur.next = cur.next.next; cur = cur.next; } return dummy.next; }

第三轮拆分是翻车重灾区。我见过很多人在拆分时把cur.next弄丢，或者拆完之后原链表也被打乱了。拆分的关键在于：在原链表上同时维护两个指针，一个沿着原节点走，一个负责把新节点串成结果链表。每处理一个原节点，先把它的复制节点接到结果链表尾部，再把原节点的 next 恢复成下个原节点，最后才移动 cur。

这个解法时间 O(n)，空间 O(1)。实际写的时候我觉得最难的不是思路，而是宁可多花一分钟把第二轮和第三轮的指针走动理清楚，也不要凭感觉写。只要有一次cur = cur.next写成了cur = cur.next.next，整个循环节奏就乱了。

2. T148 排序链表：数组思维是最大的绊脚石

2.1 为什么“转成数组再排序”不是正解

排序链表这题要求把链表升序排列，进阶要求是 O(n log n) 时间复杂度和常数级空间复杂度。

很多人的第一反应是：把链表遍历一遍丢进数组，排序好了再串成链表。这个方法在功能上当然没毛病，时间复杂度 O(n log n) 也能满足，但空间复杂度直接变成 O(n)。更关键的是，这条路完全绕开了链表操作能力。面试官出这题不是为了看你调库排数组，而是看你能不能只靠指针完成链表的二分和合并。

链表不适合快速排序的核心原因是随机访问能力弱。数组的快排可以随便取中间元素作为 pivot，可以双向扫描，链表全都做不到。就算用单向遍历的方式写快排，遇到反向递归和 pivot 选取，代码复杂度会明显上升，而且不稳定。归并排序就不一样了，它的两个核心操作是“分割”和“合并”，这两件事在链表上都只需要顺序遍历就能完成。所以链表排序的最优解，基本可以锁定归并排序。

题目要求常数级空间，所以理论上要写的是迭代版归并。递归版因为递归栈的存在，空间复杂度是 O(log n)。不过面试时通常先写递归版，再追问能不能做到 O(1) 空间，然后改成迭代版。

2.2 找中间节点：快慢指针的边界细节

归并排序第一件事是找链表中点，然后把链表从中间拆成两半。找中点用的是快慢指针，但这里有一个非常关键的小细节：快指针的初始位置。

很多教程里写的是：

ListNode slow = head; ListNode fast = head;

但如果fast从head出发，对于偶数长度的链表，比如 1 -> 2 -> 3 -> 4，slow 最终会停在 3 这个位置，分割出来的是左边 3 个、右边 1 个。这种不均匀的分割在递归中会导致非常严重的退化，最坏情况会退化成 O(n²)。

正确做法是让 fast 从 head.next 出发：

ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }

这样的效果是：奇数长度时，slow 停在正中间；偶数长度时，slow 停在左半段的最后一个节点。比如上面长度为 4 的例子，slow 会停在 2，然后把 2 的 next 断开，得到左边 [1, 2]，右边 [3, 4]，分割是均匀的。

我自己的记忆方式是：快指针只有先走一步，才能保证慢指针最终落在“偏左的中点”上。这个位置正好是左半段的末尾，断开之后递归才不会出问题。

找到中点之后，需要做两件事：第一，把中点后面的节点记下来作为右半段的头；第二，把中点节点的 next 置为 null，切断链表。

那组递归归并的完整代码是这样的：

public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode mid = slow.next; slow.next = null; ListNode left = sortList(head); ListNode right = sortList(mid); return merge(left, right); } private ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); 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; }

merge 部分有个常用细节一定要记住：最后不要写 while 循环把剩余节点一个个接到尾部，直接tail.next = (l1 != null) ? l1 : l2。因为两个链表本身是有序的，剩余部分直接接上即可，省时也省代码。

2.3 迭代归并：满足 O(1) 空间的进阶写法

递归版好写，但面试里一旦要求严格 O(1) 空间，就要上迭代归并。迭代归并的思路很朴素：先把链表看成若干个长度为 1 的子链表，相邻两组做合并；然后长度翻倍为 2，再合并；一直到整个链表合并完成。

实现时需要的一个辅助函数是 cut：从当前节点开始截取 n 个节点，并返回截取后剩余部分的头节点，同时把截断处的 next 置为 null。

private ListNode cut(ListNode head, int n) { ListNode cur = head; while (--n > 0 && cur != null) { cur = cur.next; } if (cur == null) { return null; } ListNode rest = cur.next; cur.next = null; return rest; }

完整的迭代归并代码如下：

public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } int length = 0; ListNode cur = head; while (cur != null) { length++; cur = cur.next; } ListNode dummy = new ListNode(0); dummy.next = head; for (int step = 1; step < length; step <<= 1) { ListNode prev = dummy; ListNode headCur = dummy.next; while (headCur != null) { ListNode left = headCur; ListNode right = cut(left, step); headCur = cut(right, step); prev.next = merge(left, right); while (prev.next != null) { prev = prev.next; } } } return dummy.next; }

这段代码里最需要讲清楚的是 while 循环内部的顺序。当前这一轮要处理的是从头开始的两段，每段长度为 step。先取出 left，然后cut(left, step)得到 right，再cut(right, step)得到下一轮要处理的头节点 headCur。这个顺序不能变，因为 merge 会修改 left 和 right 的 next 指针，如果不先把 headCur 保存下来，merge 之后你就找不到后面还没排序的部分了。

prev.next = merge(left, right)之后，prev 要移动到合并后的末尾，方便下一组接上。这里我用了一个 while 循环找到尾部，但其实在 merge 里可以让它返回尾节点，或者直接在合并过程中维护尾指针。每次 while 循环走到末尾，不过因为合并段长度最多是 2 * step，总长度是 n，所有轮次加起来的复杂度还是 O(n log n)，只是常数略大。面试时写这个版本，重点是把逻辑讲清楚，代码次之。

迭代版的寻找边界问题也容易踩坑，我建议自己画一个长度为 5 或 6 的链表，手动跑一遍 step = 1、2、4 的过程，很快就能理解为什么最后一步 step < length 而不是 <=。

3. 两道题放在一起练，真正沉淀下来的三个通用技巧

3.1 哨兵节点：打破“头节点需要特殊处理”的魔咒

T138 原地法的第三轮拆分，以及 T148 的迭代归并，都用到了哨兵节点（dummy node）。为什么需要它？因为在这两个场景里，结果链表的头节点是变化的。

T148 排序完之后，原来的 head 不一定是整个链表的头了，最小值可能出现在链表中间。如果用普通变量维护头节点，每次合并都要单独判断头节点是否为空，代码会变得很啰嗦。T138 拆链时，结果链表的头就是原链表第二个节点，单独处理也很别扭。

做法就是统一创建一个 dummy 节点，让它的 next 指向真正的头，操作过程中始终用dummy.next作为最终结果。循环里的 prev 从 dummy 开始，这样第一个节点天然不需要特殊判断。

我见过不少初学者觉得 dummy 是多余变量，能省就省。但链表题里，多一个 dummy 节点能让代码的健壮性提升一个档次，尤其是头节点可能被修改的场景，强烈建议直接用。

3.2 快慢指针：不同初始位置对应不同需求

快慢指针在这两题里都有出现，但初始位置不同。T138 里没有快慢指针，T148 里找中点时 fast 从 head.next 出发，为了拿到偏左的中点。

快慢指针还有一种常见写法是fast = head，那样 slow 最终会停在中点的右侧。在一些只需要判断“是否到达中点”但不需要准确断开位置的场景下没问题，比如判断回文链表时，我们只需要找到中间位置然后从那里开始比较。但排序链表这种需要把两边都递归处理的场景，断开的位置如果偏了，递归深度和性能都会出问题。

所以我的经验是：需要把链表均匀拆成两半时，快指针从 head.next 出发；只需要定位中间节点时，快指针从 head 出发就行。

3.3 链表 debug 的土办法：写一个打印函数

链表题最难受的地方在于，你很难直接看到当前链表结构长什么样，不像数组那样可以随手打印。我在刷这两道题的时候，自己写了一个printList的工具方法，专门用来调试。

private String listToString(ListNode head) { List<String> values = new ArrayList<>(); ListNode cur = head; while (cur != null) { values.add(String.valueOf(cur.val)); cur = cur.next; } return String.join(" -> ", values); }

调试 T148 时，在每次 merge 前后打印；调试 T138 时，除了打印 next 指向的序列，也可以打印每个节点 random 指向的 val。多亏这个工具，我才在一次调试中发现了 T138 原地法拆分时指针走乱的问题。

调试 T138 还有一个更严格的方法：打印旧链表头和新链表头的第一个节点地址。如果地址有交集，说明深拷贝没有完全独立，某个指针还是指向了原链表节点。这对验证 random 指针尤其有效，因为肉眼很容易忽略。

4. 面试追问、边界条件与我的翻车记录

4.1 T138 的 random 指向自己，原地法别写错

random 指向自身不算罕见情况，比如一个节点的 random 指向自己。哈希表法完全不会被这种东西影响，因为所有映射关系都建好了。

但原地穿插法需要小心。第二轮回合里，如果cur.random == cur，那么cur.random.next是什么？

因为我们在第一轮已经把复制节点插到了每个原节点的后面，所以cur.next就是 cur 的复制节点。此时cur.random.next也就是cur.next，正好是 cur 自己的复制节点。所以复制节点的 random 会正确地指向它自己。

这个逻辑听起来顺，但写的时候很容易被绕进去。我的建议是，遇到“指向自己”的用例，自己在纸上画一下 1 -> 1' 这两个节点的关系，再动笔写。死记结论不如理解一遍。

4.2 T148 的边界，长度不是 2 的幂才是常态

很多人在 T148 上翻车，不是因为主流程没写对，而是链表长度不是 2 的幂的时候，cut 和 merge 怎么截断，容易想不清楚。

比如长度为 5 的链表，step = 1 时，最后一组只有一个节点，它没有右边的合并对象，所以直接单独留在那里。step = 2 时，会有一部分节点已经合并过，有一部分还没合并。迭代代码里while (headCur != null)的循环条件保证了这一点：只要当前还有节点没处理，就继续取两段，哪怕第二段是 null，merge 也能正确处理。

如果 merge 里写的是while (l1 != null && l2 != null)，最后又tail.next = (l1 != null) ? l1 : l2，那么即使 right 是 null，也只会把 left 直接接上，没有问题。这个设计是我觉得迭代归并最优雅的地方：它根本不需要关心剩余段是否完整，只需要保证每一轮能处理到链表末尾。

递归版也是一样，递归终止条件head == null || head.next == null天然覆盖了空链表和单节点的场景。注意这里不能只写head.next == null，空链表直接返回 head 即可。

4.3 现场经验：我踩过的一个坑，希望你别踩

我第一次写 T138 原地法时，第三轮拆分写成了这样：

while (cur != null) { tail.next = cur.next; cur.next = cur.next.next; cur = cur.next; // 这里已经错了 tail = tail.next; }

问题出在cur = cur.next这一行。这行代码想移动 cur 到下一个原节点，但此时cur.next已经被上一行改成了“原链表的下一个原节点”吗？

回顾第三轮的操作：先让 tail.next 指向 cur.next，也就是复制节点；然后把 cur.next 指向了 cur.next.next，也就是下一个原节点。到这里，cur.next 确实已经指向下一个原节点了，所以cur = cur.next在逻辑上看起来是对的。但你漏了 tail，tail 的移动顺序不对，导致 tail 没有指向正确的尾部，整个结果链表会断掉。

正确的顺序是：先移动 tail 到复制节点，处理原节点的 next，再移动 cur。每一步都要想清楚“当前这个节点往后，还有哪些指针没被访问过”。如果你发现自己在写循环时，对指针下一步去哪需要犹豫，就停下来把节点画出来，千万别硬写。

T138 和 T148 这两道题我后来通过重复默写的方式，把错误彻底消除了。我的默写标准是“不看任何资料，在白板上完整写出两种解法的核心代码，并且能口头解释每一行指针移动的理由”。

如果能在 10 分钟内写完，说明这道题已经转化为肌肉记忆了。面试前拿这两题热手，比临场刷十个新题更有用。链表题的代码量不算大，但每一步都是细节，写多了你会发现“手动改指针”其实是一件很自然的事，而这两道题正是帮你建立这种感觉的上好素材。