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.
分析
深度复制一个链表，需要每个节点都要重新new，然后各个指针分别对应。其中每个节点存在一个随机指针，我是挨个遍历寻找新的链表对应的随机指针，效率很低。网上有些做法是用map或table来辅助，提高效率。
还有个方法是：
Step 1: create a new node for each existing node and join them together
eg: A->B->C will be A->A'->B->B'->C->C'
Step2: copy the random links: for each new node n', n'.random = n.random.next
Step3: detach the list: basically n.next = n.next.next; n'.next = n'.next.next
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* struct RandomListNode *next;
* struct RandomListNode *random;
* };
*/
struct RandomListNode *copyRandomList(struct RandomListNode *head) {
if(head==NULL)return NULL;
struct RandomListNode *answer=(struct RandomListNode *)malloc(sizeof(struct RandomListNode ));
answer->label=head->label;
struct RandomListNode *p1=head->next,*p2=answer,*p3,*p4;
while(p1!=NULL)
{
struct RandomListNode *node=(struct RandomListNode *)malloc(sizeof(struct RandomListNode ));
node->label=p1->label;
p2->next=node;
p1=p1->next;
p2=p2->next;
}
p2->next=NULL;
p1=head;
p2=answer;
while(p1!=NULL)
{
p3=head;
p4=answer;
while(p3!=p1->random)
{
p3=p3->next;
p4=p4->next;
}
p2->random=p4;
p1=p1->next;
p2=p2->next;
}
return answer;
}
