138. 复制带随机指针的链表

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head)   return NULL;
        for(auto p=head;p;p=p->next->next)//复制小弟
        {
            auto t=new Node(p->val);
            t->next=p->next;
            p->next=t;
        }
        for(auto p=head;p;p=p->next->next)//复制random
            if(p->random)
                p->next->random=p->random->next;
        //抽出链表
        auto dummy=new Node(-1),tail=dummy;
        for(auto p=head;p;p=p->next)
        {
            //将小弟节点插入新链表
            auto new_node=p->next;
            tail=tail->next=new_node;
            //将原链表恢复
            p->next=p->next->next;
        }
        return dummy->next;
    }
};