LeetCode 剑指 Offer 35. 复杂链表的复制

约 5 分钟
文章信息 12 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 美团 阿里巴巴 快手 百度 剑指 Offer 剑指 Offer（第 2 版）
标签
哈希表 链表
目录

题目描述

✅ 剑指 Offer 35. 复杂链表的复制

image-20241107210752470

题意分析

给一条链表，每个节点除了常规的 next，还多一个 random 指针，它可以指向链表里的任意一个节点，也可以为空，甚至可以指向自己。要求做深拷贝：返回一条结构完全一致的新链表，且新链表里的每一个节点都必须是全新创建的，不能有任何一个节点是原链表里的。判题会检查这一点，返回原链表或者混用原节点都算错。

约束信号：节点数最多 1000，值的范围允许重复。「值可以重复」这一条很关键——它意味着不能用节点值来标识一个节点，必须按节点身份（也就是引用/指针本身）来对应，否则两个值相同的节点会被混为一谈。

边界有三处：空链表要返回空；只有一个节点且 random 指向自己；random 为空时，拷贝出来的 random 也必须是空，而不是某个凑数的节点。

解法：交织链表原地复制

核心思路

哈希表能用「原节点 → 复制节点」完成映射，但需要 $O(n)$ 额外空间。更适合追问的做法，是把映射直接编码进链表结构：在每个原节点后插入它的复制节点。

交织后结构为 A → A' → B → B' → ...，于是任意原节点 x 的复制节点恒为 x.next。若 A.random = B，那么 A'.random 就是 B.next，即 A.random.next。完成随机指针后，再把奇数位置的原节点和偶数位置的复制节点拆成两条链。

三趟遍历各有一个不变量：第一趟后每个原节点紧跟自己的副本；第二趟后每个副本的 random 已指向副本而非原节点；第三趟在恢复原链的同时连接复制链。算法结束时原链必须与输入前完全一致。

解题步骤

  1. 交织节点：对每个原节点 cur 创建 copy，插到 cur 与原来的 cur.next 之间。
  2. 复制随机指针：复制节点是 cur.next；当 cur.random 非空时，令 cur.next.random = cur.random.next。
  3. 拆分链表：保存下一个原节点，恢复 cur.next，再把当前复制节点接到下一个复制节点。
  4. 返回最初的 head.next；空链表直接返回空。

例如原链为 A → B 且 A.random = B。交织后为 A → A' → B → B'，因此 A'.random = A.random.next = B'。拆分后得到恢复的 A → B 与独立的 A' → B'。

代码实现

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) {
            cur.next.random = cur.random == null ? null : cur.random.next;
        }

        Node copiedHead = 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 copiedHead;
    }
}

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

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

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

    copiedHead := head.Next
    for cur := head; cur != nil; {
        copy := cur.Next
        nextOriginal := copy.Next
        cur.Next = nextOriginal
        if nextOriginal != nil {
            copy.Next = nextOriginal.Next
        }
        cur = nextOriginal
    }
    return copiedHead
}

复杂度分析

  • 时间复杂度：$O(n)$，三趟遍历均只处理每个节点一次。
  • 空间复杂度：$O(1)$，除返回链表所需的新节点外，只使用常数个指针，没有哈希表或递归栈。

关键点总结

  • 交织结构把映射关系变成 original.next == copy，省掉哈希表。
  • copy.random = original.random.next 的前提是所有复制节点已经交织完成。
  • 拆链必须同时恢复原链和连接复制链，不能只取出复制节点。
  • 该方法会暂时修改输入，但返回前完全恢复；若输入在遍历期间可能被并发读取，应使用哈希表方案。

易错点总结

  • 给 random 赋值时漏判空，会在 original.random == null 时解引用空指针。
  • 写成 copy.random = original.random 会让新旧链表共享节点，不是深拷贝。
  • 第二趟若按 cur = cur.next 前进，会走到复制节点；原节点之间应跨两步移动。
  • 拆链时只恢复原链、不设置 copy.next，复制链会断开；只连接复制链、不恢复原链，则破坏输入。

相似题目

题目 难度 考察点
138. 随机链表的复制 中等 同题的英文站版本
133. 克隆图 中等 带环结构的深拷贝与去重
206. 反转链表 简单 链表指针的就地改写
141. 环形链表 简单 用快慢指针检测环
21. 合并两个有序链表 简单 双链表归并与哨兵节点