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

2023-09-27 HGNULB 约 5 分钟

文章信息 12 个分类 · 2 个标签

分类

LeetCode CodeTop 中等 未解决 10-20 剑指 Offer 剑指 Offer（第 2 版） 字节 阿里 美团 百度 快手

标签

哈希表 链表

题目描述

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

题意分析

每个节点都有 next 和 random 两条引用，其中 random 可以指向链表中的任意节点，也可以为空。复制后，节点值和引用关系都要保持，但所有非空引用必须指向新节点。

难点不在创建节点，而在找到 random 目标的副本。对应关系必须按节点身份建立，不能按节点值建立，因为不同节点可能具有相同的值。

解法：交织链表原地复制

核心思路

[!blue]

不另建映射表，而是把每个副本插到对应原节点后面，使 original.next 始终指向它的副本。这样，若原节点的随机目标是 original.random，目标的副本就是 original.random.next。

必须先创建全部副本，再统一设置随机指针：随机目标可能在当前节点之前或之后，也可能是当前节点本身，只有交织完成后，这些目标的副本才都能直接找到。随机引用即使成环也不影响遍历，因为三趟遍历都只沿 next 前进。

最后拆分两条链。每轮先保存副本后的下一个原节点，再恢复当前原节点的 next，并把副本连向下一个副本。下一个原节点尚未拆分，其 next 仍是对应副本，所以两条链都能正确接续。

解题步骤

1. 空链表直接返回空。否则沿原链创建副本，把副本插在原节点后面，并通过 copy.next 前进到下一个原节点。
2. 再遍历原节点。random 为空时副本也保持为空，否则令 cur.next.random = cur.random.next；每次跨过副本前进两步。
3. 保存副本入口 copiedHead = head.next。每轮记录 copy = cur.next 和 nextOriginal = copy.next，再将原节点连回 nextOriginal，将副本连向 nextOriginal.next；到达末尾时副本的 next 为空。
4. 三趟遍历结束后，原链恢复，副本链的两类引用都只指向副本，返回 copiedHead。

代码实现

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)$，除返回链表所需的新节点外，只使用常数个指针，没有哈希表或递归栈。

关键点总结

[!green]

• 交织结构保存的是原节点到副本的对应关系，重复的节点值不会造成混淆。
• 创建副本、设置随机指针、拆分链表分成三趟，保证用到映射时映射仍完整存在。
• 拆分同时恢复原链并连接副本链；空间复杂度不计返回结果所需的新节点。

易错点总结

[!yellow]

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

相似题目

题目	难度	关联与区别
133. 克隆图	中等	随机指针让链表成为一般有向引用图，复用节点映射可保留共享与环。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/52496978

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！