# [LeetCode] Copy List with Random Pointer

Well, since we need to make a deep copy of the list and nodes in the list have a random pointer that may point to any node in the list (or NULL), we need to maintain a mapping from each node in the origianl list to the node in the copy list. If the copy of a node already exists, just use that copy without copying it again; otherwise, create a new copy and add it to the mapping.

The following code is pretty straight-forward.

 1 class Solution {
2 public:
3     RandomListNode *copyRandomList(RandomListNode *head) {
4         if (!head) return NULL;
5         mp[head] = new RandomListNode(head -> label);
6         RandomListNode* run = head;
7         RandomListNode* temp = mp[head];
8         while (run) {
9             /* Process the next pointer */
10             if (run -> next) {
11                 if (mp.find(run -> next) == mp.end())
12                     mp[run -> next] = new RandomListNode(run -> next -> label);
13                 temp -> next = mp[run -> next];
14             }
15             /* Process the random pointer */
16             if (run -> random) {
17                 if (mp.find(run -> random) == mp.end())
18                     mp[run -> random] =  new RandomListNode(run -> random -> label);
19                 temp -> random = mp[run -> random];
20             }
21             run = run -> next;
22             temp = temp -> next;
23         }
24         return mp[head];
25     }
26 private:
27     unordered_map<RandomListNode*, RandomListNode*> mp;
28 };

This code also has a very concise and easy-to-understand recursive solution as follows.

 1 class Solution {
2 public:
3     RandomListNode *copyRandomList(RandomListNode *head) {
4         if (!head) return NULL;
5         if (mp.find(head) != mp.end())
6             return mp[head];
7         RandomListNode* node = new RandomListNode(head -> label);
8         mp[head] = node;
9         node -> next = copyRandomList(head -> next);
10         node -> random = copyRandomList(head -> random);
11         return mp[head];
12     }
13 private:
14     unordered_map<RandomListNode*, RandomListNode*> mp;
15 };

This link has a clever solution using O(1) extra space, which is rewritten below in C++.

 1 class Solution {
2 public:
3     RandomListNode *copyRandomList(RandomListNode *head) {
4         if (!head) return NULL;
5         RandomListNode* run = head;
6         /* Insert the copy of each node after it. */
7         while (run) {
8             RandomListNode* copy = new RandomListNode(run -> label);
9             copy -> next = run -> next;
10             run -> next = copy;
11             run = run -> next -> next;
12         }
13         /* Set the random pointer for each copy. */
14         run = head;
15         while (run) {
16             if (run -> random)
17                 run -> next -> random = run -> random -> next;
18             run = run -> next -> next;
19         }
20         /* Extract the copy list. */
21         RandomListNode* new_head = new RandomListNode(0);
22         RandomListNode* new_run;
23         run = head;
24         new_head -> next = head -> next;
25         while (run) {
26             new_run = run -> next;
27             run -> next = new_run -> next;
28             if (run -> next)
29                 new_run -> next = new_run -> next -> next;
30             run = run -> next;
31         }
32         return new_head -> next;
33     }
34 };

|
10月前
|
Java
Leetcode 114. Flatten Binary Tree to Linked List

35 1
|
10月前
|
C++
Leetcode Copy List with Random Pointer（面试题推荐）

40 0
|
10月前
Leetcode 19.Remove Nth Node From End of List

31 0
|
4月前
|

leetcode-138：复制带随机指针的链表 （python中copy与deepcopy区别）
leetcode-138：复制带随机指针的链表 （python中copy与deepcopy区别）
53 0
|
4月前
|

「LeetCode合集」链表（List）及经典问题
「LeetCode合集」链表（List）及经典问题
43 0
|

LeetCode 141. 环形链表 Linked List Cycle
LeetCode 141. 环形链表 Linked List Cycle
96 0
|
Python
LeetCode 234. 回文链表 Palindrome Linked List
LeetCode 234. 回文链表 Palindrome Linked List
66 0
LeetCode 206. 反转链表 Reverse Linked List
LeetCode 206. 反转链表 Reverse Linked List
61 0
|

LeetCode 19. 删除链表的倒数第N个节点 Remove Nth Node From End of List
LeetCode 19. 删除链表的倒数第N个节点 Remove Nth Node From End of List
66 0
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III

38 6