Sign in Subscribe
算法

随机链表的复制

loser

• 9 min read
Share

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random。

该指针可以指向链表中的任何节点，也可以指向空节点。

请构造这个链表的深拷贝。

深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应原节点的值。

新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。

复制链表中的指针都不应该指向原链表中的节点。

例如，如果原链表中有 X 和 Y 两个节点，其中：

X.random -> Y

那么在复制链表中对应的两个节点 x 和 y，也应该满足：

x.random -> y

返回复制链表的头节点。

输入和输出中的链表用 n 个节点表示，每个节点用一个 [val, random_index] 表示：

  • val：表示 Node.val 的整数
  • random_index：随机指针指向的节点索引，范围从 0 到 n - 1；如果不指向任何节点，则为 null

你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

  • 0 <= n <= 1000
  • -10^4 <= Node.val <= 10^4
  • Node.random 为 null 或指向链表中的节点

解法一（哈希表）：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr)
        {
            return nullptr;
        }

        unordered_map<Node*, Node*> mp;

        Node* cur = head;
        while (cur != nullptr)
        {
            mp[cur] = new Node(cur->val);
            cur = cur->next;
        }

        cur = head;
        while (cur != nullptr)
        {
            mp[cur]->next = mp[cur->next];
            mp[cur]->random = mp[cur->random];
            cur = cur->next;
        }

        return mp[head];
    }
};

解法二（节点穿插 + 拆分）：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr)
        {
            return nullptr;
        }

        Node* cur = head;
        while (cur != nullptr)
        {
            Node* copy = new Node(cur->val);
            copy->next = cur->next;
            cur->next = copy;
            cur = copy->next;
        }

        cur = head;
        while (cur != nullptr)
        {
            if (cur->random != nullptr)
            {
                cur->next->random = cur->random->next;
            }

            cur = cur->next->next;
        }

        Node* newHead = head->next;
        cur = head;

        while (cur != nullptr)
        {
            Node* copy = cur->next;
            cur->next = copy->next;

            if (copy->next != nullptr)
            {
                copy->next = copy->next->next;
            }

            cur = cur->next;
        }

        return newHead;
    }
};

核心思想

这题和普通复制链表不同，因为每个节点除了 next 指针，还有一个 random 指针。

random 可以指向链表中的任意节点，也可以是 null。

所以复制时不能只顺着 next 创建新链表。

关键问题是：

原节点的 random 指向谁，复制节点的 random 就应该指向那个原节点对应的新节点。

也就是说，我们需要知道“原节点”和“复制节点”之间的一一对应关系。

最直观的方法是用哈希表保存这种对应关系。

进阶一点的做法是不使用哈希表，而是把复制节点临时插入到原节点后面。

这样原节点 cur 的复制节点就是：

cur->next

原节点 cur->random 的复制节点就是：

cur->random->next

什么是深拷贝

深拷贝不是只复制头指针。

也不是让新链表中的节点指向原链表中的节点。

它要求：

  • 每个原节点都有一个对应的新节点
  • 新节点的值和原节点相同
  • 新节点之间的 next 关系和原链表一致
  • 新节点之间的 random 关系和原链表一致
  • 新链表中的所有指针都不能指向原链表节点

例如原链表中：

X.random -> Y

复制后必须是：

x.random -> y

而不是：

x.random -> Y

解法一：哈希表

哈希表保存：

unordered_map<Node*, Node*> mp;

含义是：

原节点 -> 对应的新节点

第一遍遍历原链表，只创建新节点：

mp[cur] = new Node(cur->val);

此时每个原节点都有了自己的复制节点，但这些复制节点之间还没有连好。

第二遍遍历原链表，补上 next 和 random：

mp[cur]->next = mp[cur->next];
mp[cur]->random = mp[cur->random];

如果 cur->next 或 cur->random 是 nullptr，那么 mp[nullptr] 会得到空指针，对应关系也自然成立。

最后返回：

mp[head]

就是复制链表的头节点。

解法二：节点穿插

哈希表的作用是快速找到原节点对应的复制节点。

如果不想使用额外哈希表，可以把复制节点直接插入到原节点后面。

原链表：

A -> B -> C

第一步变成：

A -> A' -> B -> B' -> C -> C'

这样每个原节点的复制节点都在它后面。

也就是说：

cur->next

就是 cur 的复制节点。

如何复制 random 指针

穿插完成以后，如果原节点 cur 的随机指针指向 cur->random。

那么 cur->random 对应的复制节点就在它后面：

cur->random->next

所以复制节点的 random 应该设置为：

cur->next->random = cur->random->next;

如果 cur->random == nullptr，说明原节点没有随机指针。

复制节点的 random 也应该保持为 nullptr。

所以代码中要先判断：

if (cur->random != nullptr)
{
    cur->next->random = cur->random->next;
}

如何拆分两个链表

完成 random 指针复制以后，链表仍然是原节点和复制节点交错在一起：

A -> A' -> B -> B' -> C -> C'

需要把它拆成两条链表：

A -> B -> C
A' -> B' -> C'

对于当前原节点 cur：

  • copy = cur->next 是复制节点
  • cur->next = copy->next 可以恢复原链表
  • 如果 copy->next 不为空，那么 copy->next->next 就是下一个复制节点

所以：

cur->next = copy->next;

if (copy->next != nullptr)
{
    copy->next = copy->next->next;
}

拆分完成后，返回最开始保存的：

Node* newHead = head->next;

边界情况

如果链表为空：

head = []

直接返回 nullptr。

如果只有一个节点，并且 random == nullptr，复制后就是一个值相同、两个指针都为空的新节点。

如果只有一个节点，并且 random 指向自己，那么穿插后：

A -> A'

原节点 A.random 指向 A。

复制节点的随机指针会被设置为：

A.random->next

也就是 A'。

所以自指向的 random 也能正确复制。

正确性证明

我们证明：节点穿插解法返回的是原链表的深拷贝。

结论 1：第一遍遍历后，每个原节点后面都有一个对应的新节点

第一遍遍历时，对每个原节点 cur 创建：

Node* copy = new Node(cur->val);

并插入到 cur 后面。

因此每个原节点都有一个值相同的新节点，并且这个新节点可以通过：

cur->next

直接访问。

结论 2：第二遍遍历能正确设置所有复制节点的 random

对于任意原节点 cur，如果：

cur.random -> x

根据结论 1，节点 x 的复制节点就是：

x->next

也就是：

cur->random->next

算法设置：

cur->next->random = cur->random->next;

所以 cur 的复制节点的 random 会指向 x 的复制节点。

如果 cur->random == nullptr，复制节点的 random 保持为空，也正确。

结论 3：第三遍遍历能恢复原链表并拆出复制链表

第三遍遍历中，当前结构是：

cur -> copy -> nextOriginal

执行：

cur->next = copy->next;

可以把原节点重新连到下一个原节点。

再执行：

copy->next = copy->next->next;

可以把复制节点连到下一个复制节点。

因此原链表会被恢复，复制链表也会被正确拆出来。

结论 4：复制链表中的指针都不会指向原链表节点

复制链表中的每个节点都是通过 new Node(...) 创建的新节点。

复制节点的 next 在拆分时指向下一个复制节点。

复制节点的 random 在第二遍遍历时指向 cur->random->next，也就是某个原节点对应的复制节点。

所以复制链表中的 next 和 random 都不会指向原链表节点。

得出结论

由结论 1 可知，每个原节点都有值相同的复制节点。

由结论 2 可知，复制节点的 random 关系正确。

由结论 3 可知，复制链表的 next 关系正确，并且原链表被恢复。

由结论 4 可知，复制链表满足深拷贝要求。

因此算法正确。

举例理解

以：

head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

为例。

第一步，把复制节点插入到原节点后面：

7 -> 7' -> 13 -> 13' -> 11 -> 11' -> 10 -> 10' -> 1 -> 1'

第二步，复制 random 指针：

  • 原节点 13.random 指向 7，所以 13'.random 指向 7'
  • 原节点 11.random 指向 1，所以 11'.random 指向 1'
  • 原节点 10.random 指向 11，所以 10'.random 指向 11'
  • 原节点 1.random 指向 7，所以 1'.random 指向 7'

第三步，拆分链表：

原链表：7 -> 13 -> 11 -> 10 -> 1
复制链表：7' -> 13' -> 11' -> 10' -> 1'

复制链表的 next 和 random 结构与原链表一致，但所有节点都是新节点。

复杂度分析

解法一

需要遍历链表两次，并用哈希表保存每个原节点到复制节点的映射。

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

解法二

需要三次线性遍历：

  • 插入复制节点
  • 复制 random
  • 拆分链表

只使用常数个额外指针变量。

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

如果不把返回的新链表计入额外空间，解法二满足常数空间要求，是更推荐的做法。