# 138. Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Thoughts: O(n) time complexity, O(n) space Complexity

1. Make deep copy of each node by tying right after each node
2. Copy random pointer
3. Extract the copy list and restore the original list

Code: without dummy node (copyHead at head->next)

``````/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
RandomListNode* cur = head, *next;

// copying each node right after the current node
while(cur){
next = cur->next;
RandomListNode* copyNode = new RandomListNode(cur->label);
cur->next = copyNode;
copyNode -> next = next;
cur = next;
}

// copying random pointer

while(cur){
next = cur -> next -> next;
if(cur->random)
cur->next->random = cur->random->next; // cur->random->next is the copy of corresponding random node
// for the current node in original linked list

cur = next;
}

// extract copy list and restore original list

while(cur){
next = cur -> next -> next;
if(next) copyIter->next = next -> next;

copyIter = copyIter->next;
cur->next = next;
cur = next;
}

}
};
``````

Code: with dummy node (copyHead->next is the head->next): This one does not have to check null

T: O(n); S: O(1)

The algorithm is composed of the follow three steps which are also 3 iteration rounds.

1. Iterate the original list and duplicate each node. The duplicate of each node follows its original immediately.
2. Iterate the new list and assign the random pointer for each duplicated node.
3. Restore the original list and extract the duplicated nodes.
``````/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
*     int label;
*     RandomListNode *next, *random;
*     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
RandomListNode* cur = head, *next;
// copying each node right after the current node
while(cur){
next = cur->next;
RandomListNode* copyNode = new RandomListNode(cur->label);
cur->next = copyNode;
copyNode -> next = next;
cur = next;
}

// copying random pointer
while(cur){
next = cur -> next -> next;
if(cur->random)
cur->next->random = cur->random->next; // cur->random->next is the copy of corresponding random node
// for the current node in original linked list

cur = next;
}

// extract copy list and restore original list
RandomListNode * dummyHead = new RandomListNode(0), *copyIter = dummyHead;
while(cur){
next = cur -> next -> next;
copyIter->next = cur -> next;
copyIter = copyIter->next;

cur->next = next;
cur = next;
}

}
};
``````

Code: Copy everything from the dictionary. Space O(n)

``````# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
"""
:rtype: RandomListNode
"""
# set the default value to be changed later using collections.defaultdict ()
mapping = collections.defaultdict(lambda: RandomListNode(0))
# set the None identity mapping
mapping[None] = None

while cur:
mapping[cur].label = cur.label
mapping[cur].next = mapping[cur.next]
mapping[cur].random = mapping[cur.random]
cur = cur.next