## Wednesday, November 19, 2014

### [LeetCode] 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.

______
|           |
|          V
1->2->3

p1扫描1时，p2复制1，以及1->next (2), 1->random (3)。之后p1, p2分别移到各自的2节点。此时我们必须得知道节点3在之前已经被复制了，并且得知道复制节点的地址。
______
|           |
|          V
1->2    3

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31``` ```class Solution { public: RandomListNode *copyRandomList(RandomListNode *head) { if(!head) return NULL; unordered_map ht; RandomListNode *p1 = head; RandomListNode *p2 = new RandomListNode(head->label); ht[head] = p2; while(p1) { if(p1->next) { if(ht.count(p1->next)) p2->next = ht[p1->next]; else { p2->next = new RandomListNode(p1->next->label); ht[p1->next] = p2->next; } } if(p1->random) { if(ht.count(p1->random)) p2->random = ht[p1->random]; else { p2->random = new RandomListNode(p1->random->label); ht[p1->random] = p2->random; } } p1 = p1->next; p2 = p2->next; } return ht[head]; } }; ```

#### 1 comment:

1. 看leetcode里有一个很牛的方法实现了。Time O(n), Space O(1)