/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {//为了能够快速定位某个节点，采用确定性映射的方式，将复制链表的节点作为原链表对应节点的下一个节点
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        //每个节点指向其复制链表对应的节点，从而可以快速定位该节点
        if(!head)return NULL;
        RandomListNode *p,*q;
        p=head;
        while(p){
            q=new RandomListNode(p->label);
            q->next=p->next;
            p->next=q;
            p=q->next;
        }
        p=head;
        while(p){
            q=p->next;
            if(p->random)
                q->random=p->random->next;
            p=q->next;
        }
        p=head;
        RandomListNode*head2=p->next;
        q=head2;
        while(p){
            p->next=q->next;
            p=p->next;
            if(p){
                q->next=p->next;
                q=q->next;
            }
        }
        return head2;
    }
};

[LeetCode]Copy List with Random Pointer复杂链表的复制