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.

思路：

直接点的思路是根据原链表的next指针构建新链表，并通过一个map建立新旧链表的对应关系，再设置random指针。但是这样的问题是需要额外的map的空间。

另一个改进的方法是在原链表的节点中间插入新链表的节点，对应关系隐含在里面，最后再把两个链表拆开。

最开始一直runtime error的问题是拆开时只把新链表的关系建好了，但没有管原链表，但OJ应该对新旧链表都进行的检查。

代码：

 1     RandomListNode *copyRandomList(RandomListNode *head) {
 2         // IMPORTANT: Please reset any member data you declared, as
 3         // the same Solution instance will be reused for each test case.
 4         if(head == NULL)
 5             return NULL;
 6         RandomListNode *node = head, *tmp;
 7         while(node){
 8             tmp = new RandomListNode(node->label);
 9             tmp->next = node->next;
10             node->next = tmp;
11             node = node->next->next;
12         }
13         node = head;
14         while(node){
15             node->next->random = node->random==NULL ? NULL:node->random->next;
16             node = node->next->next;
17         }
18         node = head;
19         head = head->next;
20         while(node){
21             tmp = node->next;
22             node->next = tmp->next;
23             tmp->next = node->next==NULL ? NULL:node->next->next;
24             node = node->next;
25         }
26         return head;
27     }