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

[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 pointer13         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 links23         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     }`