LeetCode 138. 随机链表的复制

2025-08-23 HGNULB 约 5 分钟

文章信息 19 个分类 2 个标签

分类

LeetCode CodeTop 中等未解决 50-100 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度华为网易小米虾皮 LeetCode 热题 100 面试经典 150 题

题目描述

✅ 138. 随机链表的复制

题意分析

链表的每个节点除了常规的 next 指针，还多了一个 random 指针。random 不受链表顺序约束：它可以指向链表中的任意节点——前面的、后面的、甚至节点自己，也可以是 null。

要求返回这条链表的深拷贝。「深」意味着两点：其一，新链表的每个节点都必须是新创建的对象，不能复用原链表的任何节点；其二，新节点的 next 和 random 都必须指向新链表中的对应节点，不允许有任何指针指回原链表。

换句话说，判题会检查两条链表在结构上完全同构，且两组节点没有任何交集。只要有一个 random 偷懒指回了旧节点，就不算深拷贝。

边界：链表可能为空，此时直接返回空即可。

解法：原地交织复制

核心思路

问题关键：复制 next 不难，难的是找到 random 所指旧节点对应的新节点。哈希表能做映射，但要用 $O(n)$ 额外空间；面试进阶通常要求把这份映射省掉。

为什么选交织法：把每个副本插到原节点后面，形成 A -> A' -> B -> B'。这样旧节点 x 的副本恒为 x.next；若 x.random = y，则 x' 的随机指针就是 y.next，即 x.next.random = x.random.next。位置关系代替了哈希表。

不变量与正确性：第一遍后，每个旧节点后紧跟唯一副本；第二遍据此把每条旧 random 精确翻译到对应副本；第三遍按奇偶位置拆链，同时恢复旧链并连接新链。三遍结束后，新旧节点一一对应、指针结构相同，且两条链没有共享节点。

解题步骤

空链表直接返回 null。

第一遍：为每个旧节点创建副本，并插入旧节点与原后继之间。

第二遍：若 cur.random 非空，设置 cur.next.random = cur.random.next。

记录新头 head.next。第三遍同时拆出两条链：旧节点重新指向下一个旧节点，副本重新指向下一个副本。

返回新头。若不要求 $O(1)$ 额外空间，也可用两遍哈希表映射，思路更直观但空间为 $O(n)$。

代码实现

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

        for (Node cur = head; cur != null; ) {
            Node copy = new Node(cur.val);
            copy.next = cur.next;
            cur.next = copy;
            cur = copy.next;
        }

        for (Node cur = head; cur != null; cur = cur.next.next) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
        }

        Node newHead = head.next;
        for (Node cur = head; cur != null; ) {
            Node copy = cur.next;
            Node nextOriginal = copy.next;
            cur.next = nextOriginal;
            copy.next = nextOriginal == null ? null : nextOriginal.next;
            cur = nextOriginal;
        }
        return newHead;
    }
}

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }

    for cur := head; cur != nil; {
        copyNode := &Node{Val: cur.Val, Next: cur.Next}
        cur.Next = copyNode
        cur = copyNode.Next
    }

    for cur := head; cur != nil; cur = cur.Next.Next {
        if cur.Random != nil {
            cur.Next.Random = cur.Random.Next
        }
    }

    newHead := head.Next
    for cur := head; cur != nil; {
        copyNode := cur.Next
        nextOriginal := copyNode.Next
        cur.Next = nextOriginal
        if nextOriginal != nil {
            copyNode.Next = nextOriginal.Next
        }
        cur = nextOriginal
    }
    return newHead
}

复杂度分析

时间复杂度：$O(n)$，三遍线性扫描，每个节点只做常数次操作。

空间复杂度：$O(1)$，除返回结果必须创建的新节点外，只使用常数个指针。

关键点总结

交织法本质是用“副本紧跟原节点”的位置关系实现 旧节点 -> 新节点 映射。

必须等所有副本插入后再连接 random，这样任意目标的副本都已经存在。

拆链要同时完成两件事：恢复原链表、连接新链表，不能只顾返回结果。

深拷贝的检查标准是结构相同且节点集合完全不相交。

易错点总结

副本直接写 copy.random = cur.random：新链表会指回旧节点，不是深拷贝。

第一遍遍历写成普通 cur = cur.next：插入副本后会走到副本，继续复制副本并陷入死循环；应跳到 copy.next。

random == null 时仍访问 cur.random.next：会触发空指针异常。

拆链时只连接副本、不恢复旧节点的 next：原输入仍是交织结构，副作用不符合预期。

只验证值和 next：自指、前指、后指等 random 都应覆盖；例如 A.random = A 时应得到 A'.random = A'。

相似题目

题目	难度	考察点
133. 克隆图	中等	同一映射思想推广到图，需配合 DFS/BFS 防环
1485. 克隆含随机指针的二叉树	中等	树结构上的 random 深拷贝，递归 + 映射
剑指 Offer 35. 复杂链表的复制	中等	与本题同题，常以交织三步法为进阶追问