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;
}