[LeetCode] Copy List with Random Pointer, Solution

 

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]

如图分三步：

1. 插入拷贝节点

2. 复制random指针

3.分解至两个独立列表

 

[Code]

 1     RandomListNode *copyRandomList(RandomListNode *head) {
 2         //insert nodes
 3         RandomListNode * cur = head;
 4         while(cur!=NULL)
 5         {
 6             RandomListNode* temp = new RandomListNode(cur->label);
 7             temp->next = cur->next;
 8             cur->next = temp;
 9             cur = temp->next;
10         }
11         
12         // copy random pointer
13         cur = head;
14         while(cur != NULL)
15         {
16             RandomListNode* temp = cur->next;
17             if(cur->random != NULL)
18                 temp->random = cur->random->next;
19             cur = temp->next;
20         }
21         
22         //decouple two links
23         cur = head;
24         RandomListNode* dup = head == NULL? NULL:head->next;
25         while(cur != NULL)
26         {
27             RandomListNode* temp = cur->next;
28             cur->next = temp->next;
29             if(temp->next!=NULL)
30                 temp->next = temp->next->next;
31             cur = cur->next;
32         }
33 
34         return dup;
35     }