📝 题目描述

题目链接：随机链表的复制

给你一个长度为 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：

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

示例 2：

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

示例 3：

1
2
输入：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 或指向链表中的节点

💡 解题思路

方法一：两次遍历 + 哈希表

一种比较好想的方法是两次遍历法，首先创建一个哈希表 unordered_map<Node*, Node*> hash_map，第一次遍历时，我们只创建节点+复制val，不管 random 指针（因为指针指向的节点可能还没有创建），同时记录原节点和复制节点的指针到 hash_map 中。

第二次遍历时，我们做两件事情：

  • 根据原节点的连接情况，将复制节点连接起来；
  • 根据原节点的 random 指针情况，将复制节点 random 指针连接起来；

这样即可完成。

方法二：回溯 + 哈希表

我们利用回溯的方式，让每个节点的拷贝操作相互独立。对于当前节点，我们首先要进行拷贝，然后我们进行“当前节点的后继节点”和“当前节点的随机指针指向的节点”拷贝，拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。

具体地，我们用哈希表记录每一个节点对应新节点的创建情况。遍历该链表的过程中，我们检查“当前节点的后继节点”和“当前节点的随机指针指向的节点”的创建情况。如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。当我们拷贝完成，回溯到当前层时，我们即可完成当前节点的指针赋值。注意一个节点可能被多个其他节点指向，因此我们可能递归地多次尝试拷贝某个节点，为了防止重复拷贝，我们需要首先检查当前节点是否被拷贝过，如果已经拷贝过，我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。

方法三：迭代 + 节点拆分

我们首先将该链表中每一个节点拆分为两个相连的节点，例如对于链表 A→B→CA→B→C，我们可以将其拆分为 A→A′→B→B′→C→C′A→A'→B→B'→C→C'。对于任意一个原节点 SS，其拷贝节点 S′S' 即为其后继节点。

这样，我们可以直接找到每一个拷贝节点 S′S' 的随机指针应当指向的节点，即为其原节点 SS 的随机指针指向的节点 TT 的后继节点 T′T'。需要注意原节点的随机指针可能为空，我们需要特别判断这种情况。

当我们完成了拷贝节点的随机指针的赋值，我们只需要将这个链表按照原节点与拷贝节点的种类进行拆分即可，只需要遍历一次。同样需要注意最后一个拷贝节点的后继节点为空，我们需要特别判断这种情况。

🔧 代码实现

1、两次遍历 + 哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;
        unordered_map<Node*, Node*> hash_map;
        Node* ptr = head;
        // 第一次遍历，只管创建节点
        while (ptr != nullptr) {
            Node* temp = new Node(ptr -> val);
            hash_map[ptr] = temp;
            ptr = ptr -> next;
        }
        ptr = head;
        // 第二次遍历，连接节点
        while (ptr != nullptr) {
            Node* temp = hash_map[ptr];
            if (ptr -> next != nullptr) {
                temp -> next = hash_map[ptr -> next];
            }
            if (ptr -> random != nullptr) {
                temp -> random = hash_map[ptr -> random];
            }
            ptr = ptr -> next;
        }

        return hash_map[head];
    }
};

2、回溯 + 哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
// 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:
    unordered_map<Node*, Node*> hash_map;
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        if (!hash_map.count(head)) {
            Node* temp = new Node(head -> val);
            hash_map[head] = temp;
            temp -> next = copyRandomList(head -> next);
            temp -> random = copyRandomList(head -> random);
        }
        return hash_map[head];
    }
};

3、迭代 + 节点拆分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
// 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) {
        // 节点数量为0，直接返回
        if (!head) return nullptr;
        Node* ptr = head, *ptr2 = nullptr, *ans = nullptr;
        // 第一次循环，复制节点
        while (ptr != nullptr) {
            Node* temp = new Node(ptr -> val);
            Node* next = ptr -> next;
            ptr -> next = temp;
            temp -> next = next;
            ptr = next;
        }
        ans = head -> next;
        // 第二次循环，复制random指针
        ptr = head, ptr2 = nullptr;
        while (ptr != nullptr) {
            ptr2 = ptr -> next;
            if (ptr -> random) {
                ptr2 -> random = ptr -> random -> next;
            }
            ptr = ptr -> next -> next;
        }
        // 第三次循环，分离链表
        ptr = head, ptr2 = nullptr;
        while (ptr != nullptr) {
            ptr2 = ptr -> next;
            ptr -> next = ptr -> next -> next;
            ptr2 -> next =  ptr2 -> next == nullptr ? nullptr : ptr2 -> next -> next;

            ptr = ptr -> next;
        }
        return ans;
    }
};

📊 复杂度分析

1、两次遍历 + 哈希表

  • 时间复杂度：O(n)O(n)，其中 n 是链表的长度。我们只需要遍历该链表两次。
  • 空间复杂度：O(n)O(n)，其中 n 是链表的长度。为哈希表的空间开销。

2、回溯 + 哈希表

  • 时间复杂度：O(n)O(n)，其中 n 是链表的长度，对于每个节点，我们至多访问其“后继节点”和“随机指针指向的节点”各一次，均摊每个点至多被访问两次。
  • 空间复杂度：O(n)O(n)，其中 n 是链表的长度。为哈希表的空间开销。

3、迭代 + 节点拆分

  • 时间复杂度：O(n)O(n)，其中 n 是链表的长度。我们只需要遍历该链表三次。
  • 空间复杂度：O(1)O(1)，注意返回值不计入空间复杂度。

🎯 总结

  • 核心思想：节点拆分的方法要记住。