Hot 100 --- 随机链表的复制

本文概览：本文以LeetCode经典题目"随机链表的复制"为例，从随机指针带来的复制难点入手，先讲解哈希表记录新旧节点映射关系的解法，再优化到拼接+拆分的 O(1) 空间解法

一、题目

随机链表的复制题目

二、题目分析

给定一个链表，每个节点除了 next 指针之外，还有一个 random 指针，random 可以指向链表中的任意节点，也可以指向 null

目标：对这个链表进行深拷贝，返回复制链表的头节点

核心难点：普通链表复制并不难，难的是 random 指针。因为新节点的 random 必须指向新链表中的对应节点，不能继续指向旧链表中的节点

思路概览

最终优化版 Java 实现代码如下

public Node copyRandomList(Node head) {
    if (head == null) return null;

    Node cur = head;

    // 拼接新节点到原节点后面
    while (cur != null) {
        Node newNode = new Node(cur.val);
        newNode.next = cur.next;
        cur.next = newNode;
        cur = newNode.next;
    }

    // 处理随机指针
    cur = head;
    while (cur != null) {
        if (cur.random != null) {
            // 新节点的随机指针指向旧节点的随机指针的下一个节点
            cur.next.random = cur.random.next;
        }
        // 移动到下一个旧节点
        cur = cur.next.next;
    }

    // 分离新旧节点
    cur = head.next;
    Node pre = head, res = head.next;
    while (cur.next != null) {
        // 分离新旧节点
        pre.next = pre.next.next;
        cur.next = cur.next.next;
        // 移动到下一个节点
        pre = pre.next;
        cur = cur.next;
    }
    pre.next = null; // 单独处理原链表尾节点
    // 返回新节点的头节点
    return res;
}

思路简要说明

复制节点并拼接：把每个新节点都插入到对应旧节点的后面，形成 旧1 → 新1 → 旧2 → 新2 的结构
设置 random 指针：旧节点的复制节点是 cur.next，旧节点 random 指向节点的复制节点是 cur.random.next
拆分新旧链表：把拼接在一起的新旧节点拆开，恢复旧链表，同时得到新链表

三、思路详解

普通链表复制为什么不难？

如果链表只有 next 指针，复制其实很简单：遍历旧链表，每遇到一个旧节点，就创建一个值相同的新节点，然后把新节点接到新链表后面即可

比如：

1 2	旧链表：A → B → C 新链表：A' → B' → C'

只要按顺序复制 next 关系即可

但是这道题多了一个 random 指针，问题就复杂了

random 指针带来的问题

random 指针可以指向链表中的任意节点

比如：

旧链表 next：   A → B → C
random关系：    A.random → C
               B.random → A
               C.random → B

复制后应该是：

新链表 next：   A' → B' → C'
random关系：    A'.random → C'
               B'.random → A'
               C'.random → B'

注意：新链表的 random 必须指向新节点，不能指向旧节点

这就带来一个问题：当我们复制 A' 的时候，如果 A.random 指向 C，那么 A'.random 应该指向 C'。可是这时候 C' 可能还没创建，所以无法直接找到。问题就演变成了：如何快速找到旧节点 C 对应的新节点 C'？

如果没有记录新旧节点的对应关系，就只能每次从头遍历链表去找，这样会非常低效

暴力思路：每次都遍历查找

最直接的做法是：

先复制一条只有 next 的新链表
设置 random 指针时，对于旧链表中的每个 random 指向，都从旧链表头开始找它是第几个节点
再到新链表中走同样的步数，找到对应的新节点并赋值

这个方法虽然能做，但问题很明显：每个节点设置 random 时都可能要遍历一整条链表

时间复杂度：O(n²)
空间复杂度：O(1) 或 O(n)，取决于是否额外存储链表
核心瓶颈：没有记录旧节点和新节点之间的对应关系，所以每次都要重新查找

关键思考：能不能提前记录好"旧节点 → 新节点"的关系？这样设置 random 时就能直接拿到对应的新节点

方法一：哈希表记录新旧节点关系

最自然的优化就是使用哈希表

哈希表中记录：

1
2
3

旧节点 A → 新节点 A'
旧节点 B → 新节点 B'
旧节点 C → 新节点 C'

这样设置 random 时，如果旧节点 cur.random 指向 C，那么新节点的 random 就应该指向 map.get(C)，也就是 C'

实现步骤

第一遍遍历旧链表，创建所有新节点，并用哈希表记录新旧节点关系
第二遍遍历旧链表，根据哈希表补全新节点的 next 和 random

Java 实现代码如下

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) {
        Node newNode = map.get(cur);
        newNode.next = map.get(cur.next);
        newNode.random = map.get(cur.random);
        cur = cur.next;
    }

    return map.get(head);
}

为什么 map.get(null) 没问题？

在 Java 的 HashMap 中，map.get(null) 会返回 null。所以当 cur.next == null 或 cur.random == null 时，直接赋值为 null，逻辑刚好正确

这个方法非常清晰，但需要额外的哈希表：

时间复杂度：O(n)
空间复杂度：O(n)

如果想继续优化空间，就需要想办法不用哈希表也能维护新旧节点的对应关系

方法二：拼接 + 拆分

哈希表的作用是记录：旧节点和新节点之间的对应关系

那有没有办法不用哈希表，也能快速找到某个旧节点对应的新节点？

答案是：把新节点直接插到旧节点后面

比如原链表是：

A → B → C

复制并拼接后变成：

1	A → A' → B → B' → C → C'

这样就天然建立了对应关系：

1
2
3

旧节点 A 的复制节点就是 A.next
旧节点 B 的复制节点就是 B.next
旧节点 C 的复制节点就是 C.next

这就相当于把哈希表的信息直接塞进链表结构里了

第一步：拼接新节点

遍历旧链表，每遇到一个旧节点 cur，就创建一个新节点 newNode，然后把它插到 cur 后面

Node newNode = new Node(cur.val);
newNode.next = cur.next;
cur.next = newNode;
cur = newNode.next;

图示：

原链表：
A → B → C

处理 A 后：
A → A' → B → C

处理 B 后：
A → A' → B → B' → C

处理 C 后：
A → A' → B → B' → C → C'

这一步完成后，每个旧节点的下一个节点就是它对应的新节点

第二步：处理 random 指针

拼接完成后，random 指针就很好处理了

如果当前旧节点是 cur：

cur.next 是当前旧节点对应的新节点
cur.random 是旧节点 random 指向的旧节点
cur.random.next 就是这个 random 目标节点对应的新节点

所以：

1	cur.next.random = cur.random.next;

图示理解：

旧链表关系：
A.random → C

拼接后：
A → A' → B → B' → C → C'
|___________________↑
 A.random 指向 C

因为 C 的复制节点就在 C 后面，所以：
A'.random = A.random.next = C'

也就是：

1
2
3

cur.next.random = cur.random.next
  ↑                 ↑
 A'                C'

如果 cur.random == null，说明当前节点没有 random 指向，直接跳过即可

第三步：拆分新旧链表

拼接后的链表是：

1	A → A' → B → B' → C → C'

我们需要拆成两条链表：

1 2	旧链表：A → B → C 新链表：A' → B' → C'

代码中：

cur = head.next;
Node pre = head, res = head.next;
while (cur.next != null) {
    pre.next = pre.next.next;
    cur.next = cur.next.next;
    pre = pre.next;
    cur = cur.next;
}
pre.next = null;
return res;

这里的指针含义是：

pre：旧链表当前节点
cur：新链表当前节点
res：新链表头节点，也就是 head.next

为什么 res = head.next？

因为拼接完成后，原头节点 head 后面紧跟的就是复制出来的新头节点，所以新链表的头节点就是 head.next

拆分过程图示

初始：

pre
 ↓
A → A' → B → B' → C → C'
    ↑
   cur

res = A'

第一轮：

1 2	pre.next = pre.next.next; // A.next = B，恢复旧链表连接 cur.next = cur.next.next; // A'.next = B'，连接新链表

变成：

1 2	旧链表：A → B → B' → C → C' 新链表：A' → B' → C → C'

然后移动：

1 2	pre = pre.next; // pre = B cur = cur.next; // cur = B'

第二轮继续拆分，直到新链表最后一个节点

最后需要：

1	pre.next = null;

这是为了恢复旧链表尾节点的 next。否则旧链表尾节点可能还指向最后一个复制节点

最终得到：

1 2	旧链表：A → B → C 新链表：A' → B' → C'

时间复杂度：O(n)，三次遍历链表
空间复杂度：O(1)，没有使用哈希表，只使用几个指针变量

四、总结

这道题的核心不是普通的链表复制，而是如何处理 random 指针

关键点是：必须建立旧节点和新节点之间的对应关系

哈希表方法：显式维护 旧节点 → 新节点 的映射，思路清晰，但空间复杂度 O(n)
拼接+拆分方法：把新节点插到旧节点后面，利用链表结构隐式维护映射，空间复杂度 O(1)

拼接法最巧妙的地方就在于：旧节点的复制节点就是旧节点的 next，旧节点 random 指向节点的复制节点就是 random.next