随机链表的复制 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

题意

深拷贝一个链表，要求新链表中的每个节点都是新创建的，并且这些节点的 $random$ 指针都指向新链表中的相应节点。

思路

如果没有 $random$ 指针，只需在遍历链表的同时，依次复制每个节点（创建新节点并复制 $val$ ），添加在新链表的末尾。

有 $random$ 指针，问题就变得复杂了，我们需要知道 $random$ 指向的那个节点，在新链表中是哪个节点。

所以必须记录原链表节点到新链表节点的映射（map）。这样可以通过原链表 $random$ 指向的节点，知道新链表的 $random$ 应该指向哪个节点。

难道要用哈希表吗？不需要，我们可以把新链表和旧链表「混在一起」。

例如链表 $1 \to 2 \to 3$ ，依次复制每个节点（创建新节点并复制 $val$ 和 $next$ ），把新节点直接插到原节点的后面，形成一个交错链表：

1 \to 1^{'} \to 2 \to 2^{'} \to 3 \to 3^{'}

如此一来，原链表节点的下一个节点，就是其对应的新链表节点了！

然后遍历这个交错链表，假如节点 $1$ 的 $random$ 指向节点 $3$ ，那么就把新节点 $1^{'}$ 的 $random$ 指向节点 $3$ 的下一个节点 $3^{'}$ ，这样就完成了对 $random$ 指针的复制。

最后，从交错链表中分离出 $1^{'} \to 2^{'} \to 3^{'}$ ，即为深拷贝后的链表。做法类似 328. 奇偶链表。

⚠注意：不能只删除节点 $1, 2, 3$ ，因为题目要求原链表的 $next$ 不能修改。（用 Python 的同学可以先看第一份代码，再看第二份代码）

Python 解法1C++ 解法1

python

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        # 复制每个节点，把新节点直接插到原节点的后面
        cur = head
        while cur:
            cur.next = Node(cur.val, cur.next)
            cur = cur.next.next

        # 遍历交错链表中的原链表节点
        cur = head
        while cur:
            if cur.random:
                # 要复制的 random 是 cur.random 的下一个节点
                cur.next.random = cur.random.next
            cur = cur.next.next

        # 删除交错链表中的原链表节点，剩下的节点即为新链表
        cur = dummy = Node(0, head)
        while cur.next:
            # 删除原链表的节点，即当前节点的下一个节点
            # 如果要恢复原链表，见另一份代码【Python3 写法二】
            cur.next = cur.next.next
            cur = cur.next

        return dummy.next

cpp

// C++ 版待补充

Python 解法2C++ 解法2

python

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        # 复制每个节点，把新节点直接插到原节点的后面
        cur = head
        while cur:
            cur.next = Node(cur.val, cur.next)
            cur = cur.next.next

        # 遍历交错链表中的原链表节点
        cur = head
        while cur:
            if cur.random:
                # 要复制的 random 是 cur.random 的下一个节点
                cur.next.random = cur.random.next
            cur = cur.next.next

        # 把交错链表分离成两个链表
        tail = dummy = Node(0, head)
        cur = head
        while cur:
            copy = cur.next  # 新节点
            tail.next = copy  # 把新节点插在 tail 的后面，构建新的链表
            cur.next = copy.next  # 恢复原节点的 next
            cur = cur.next
            tail = tail.next

        return dummy.next

cpp

// C++ 版待补充

C++ 解法3

cpp

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 复制每个节点，把新节点直接插到原节点的后面
        for (Node* cur = head; cur; cur = cur->next->next) {
            cur->next = new Node(cur->val, cur->next, nullptr);
        }

        // 遍历交错链表中的原链表节点
        for (Node* cur = head; cur; cur = cur->next->next) {
            if (cur->random) {
                // 要复制的 random 是 cur->random 的下一个节点
                cur->next->random = cur->random->next;
            }
        }

        // 把交错链表分离成两个链表
        Node dummy(0);
        Node* tail = &dummy;
        for (Node* cur = head; cur; cur = cur->next, tail = tail->next) {
            Node* copy = cur->next; // 新节点
            tail->next = copy; // 把新节点插在 tail 的后面，构建新的链表
            cur->next = copy->next; // 恢复原节点的 next
        }

        return dummy.next;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是链表的长度。
空间复杂度： $O (1)$ 。返回值不计入。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

题意 ​

思路 ​

复杂度分析 ​

分类题单 ​

题意

思路

复杂度分析

分类题单