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

思路：

这题的关键是如何track一个节点是否已经被copy了。假如我们要copy如下list，用指针p1来扫描每个节点，另一个指针p2建立copy。

______

|           |

|          V

1->2->3

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

______

|           |

|          V

1->2    3 

所以这里可以使用一个hash table来记录原节点和复制节点的地址对应关系。这样每次要建立当前节点p的next和random前，先在hash table中查找。如果找到，则直接连接；否则建立新节点连上，并把和原节点的对应关系存入hash table中。

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<RandomListNode*, RandomListNode*> 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]; } };