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.

Shallow copy:

Some members of the copy may reference the same objects as the original.

Deep copy:

All members of the original are cloned. There are no shared objects.

主要区别在于拷贝之后指针成员指向的是不是同一个地址。

这道题最naive的方法就是用一个unordered_map来存original pointer和copied pointer的对应关系。空间复杂度o(n),时间复杂度o(n)。

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

比较smart的方法是，将copied node放在对应的original node后面,也就是original node1->copied node1->original node2->copied node2->....

然后就可以用p->random->next来求得random的新地址了。 

最后再把copied list和original list分离开。

以后如果有题目需要把两个list对应起来的话，可以采用相同的方式，把它们串起来。

1 RandomListNode *copyRandomList(RandomListNode *head) { 2     if(head == NULL) return NULL; 3     RandomListNode *p = head; 4     do { 5         RandomListNode *q = p->next; 6         p->next = new RandomListNode(p->label); 7         p->next->next = q; 8         p = q; 9     } while(p != NULL);10     p = head;11     do {12         p->next->random = (p->random == NULL) ? NULL : p->random->next;13         p = p->next->next;14     } while(p != NULL);15     p = head;16     RandomListNode *r = head->next;17     for(RandomListNode *q = r;;) {18         p->next = q->next;19         p = p->next;20         if(p == NULL) break;21         q->next = p->next;22         q = q->next;23     }24     return r;25 }