计算机科学基础leetcode刷题链表
Source
Edit
History

138. 随机链表的复制

Problem: 138. 随机链表的复制

解题方法

  • 哈希表存储对应源Node为键,拷贝Node为值

  • 递归添加Next和random

  • 需要注意拷贝的时head的next和random不是node的

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

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:

    unordered_map<Node*, Node*> dic;

    Node* copyRandomList(Node* head) {

        if (head == nullptr)

            return nullptr;

        if (dic.find(head) == dic.end()) {

            Node* node = new Node(head->val);

            dic[head] = node;

            node->next = copyRandomList(head->next);

            node->random = copyRandomList(head->random);

        }

        return dic[head];

    }

};
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
public class Solution {

    Dictionary<Node,Node> dict = new Dictionary<Node,Node>();

    public Node CopyRandomList(Node head) {

        if(head==null)return null;

        if(!dict.ContainsKey(head)){

            Node node = new Node(head.val);

            dict.Add(head,node);

            node.next = CopyRandomList(head.next);

            node.random = CopyRandomList(head.random);

        }

        return dict[head];

    }

}