【算法笔记】LeetCode_138 随机链表的复制

LeetCode_138 随机链表的复制

LeetCode_138 随机链表的复制

题目描述

给你一个长度为 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<sup>4</sup> <= Node.val <= 10<sup>4</sup>
• Node.random 为 null 或指向链表中的节点。

思路

本题最基本的目的很简单，即 “拷贝链表”，题目中唯二的两个难点即是“深拷贝”和“随机子节点”

1. 深拷贝：深拷贝即新的对象和原始对象无任何依赖和关联，需要新开辟内存
2. 随机子节点：随机子节点的引入使得任意一个节点都有被多次创建的机会，即上一个节点的next，以及任意一个节点的random都有机会创建

那么我们面对两个问题：

1. 如果当前节点的random节点是已经遍历过的节点，如何根据原始链表的random地址获取新创建的节点地址
2. 如果当前节点的random节点是还未创建的节点，那么创建出新的节点后如何告诉将来遍历到它的位置的时候的next指针：我已经被创建过了，不应该再被创建，你需要直接连接

考虑到这里，我考虑使用哈希表来存储每个已创建的节点的原始地址和新地址，每次遍历的时候，查找当前节点和random节点是否已创建，是的话直接连接，否的话新建，然后添加进哈希表

代码解析

/*
// 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) {
        // 创建一个哈希表，用于存储原节点和复制节点的映射关系
        unordered_map<void*, void*> ptrMap;
        // 对于空指针也建立映射关系，确保后续处理的一致性
        ptrMap[nullptr] = nullptr;
      
        // 创建一个临时节点，用于构建新的链表
        Node tmp(0);
        Node * ret = &tmp; // ret指向新链表的头部
      
        // 遍历原链表
        while(head != nullptr)
        {
            // 检查原节点是否已经在哈希表中
            auto newAdress = ptrMap.find(head);
            Node * currentNode;
            if (newAdress == ptrMap.end())
            {
                // 如果不在，则创建新节点，并建立映射关系
                currentNode = new Node(head->val);
                ptrMap[head] = currentNode;
            }
            else
            {
                // 如果在，则直接获取映射的新节点
                currentNode = (Node *)newAdress->second;
            }
          
            // 同样的方式检查原节点的random指针指向的节点
            auto randomNodeAdress = ptrMap.find(head->random);
            Node * randomNode;
            if (randomNodeAdress == ptrMap.end())
            {
                // 如果不在，则创建新节点，并建立映射关系
                randomNode = new Node(head->random->val);
                ptrMap[head->random] = randomNode;
            }
            else
            {
                // 如果在，则直接获取映射的新节点
                randomNode = (Node *)randomNodeAdress->second;
            }
          
            // 设置新节点的random指针
            currentNode->random = randomNode;
          
            // 将新节点连接到新链表的尾部
            ret->next = currentNode;
            ret = ret->next;
          
            // 继续遍历原链表的下一个节点
            head = head->next;
        }
      
        // 返回新链表的头部（跳过临时节点）
        return tmp.next;
    }
};
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

思想：

这段代码使用哈希表来存储原链表节点和复制后新链表节点的映射关系。通过遍历原链表，对于每个节点，先检查它是否已经在哈希表中，如果在则直接取出新节点，如果不在则创建新节点并添加到哈希表中。同时，对于每个节点的random指针指向的节点也进行同样的处理。最后，将新节点按照原链表的顺序连接起来，形成新的链表。

方法：

• 使用哈希表ptrMap存储原节点和新节点的映射关系。
• 遍历原链表，根据映射关系创建新节点，并设置新节点的random指针。
• 将新节点连接到新链表的尾部。

时间复杂度：

• 遍历原链表一次，时间复杂度为O(n)，其中n为原链表的长度。
• 对于每个节点，哈希表的查找、插入和取值操作平均时间复杂度为O(1)。
• 因此，总时间复杂度为O(n)。

空间复杂度：

• 使用了哈希表ptrMap来存储原节点和新节点的映射关系，最坏情况下需要存储所有节点，空间复杂度为O(n)。
• 创建了新链表，其空间复杂度也为O(n)。
• 因此，总空间复杂度为O(n)。