Google+ Followers

Sunday, November 17, 2013

[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.分解至两个独立列表

 

image

[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 }

Post a Comment