/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {

        if(!head) return head;
        for(auto p = head;p;){
            auto next = p->next;
            auto np = new ListNode(p->val);
            p->next = np;
            np->next = next;
            p = p->next->next;
        }

        for(auto p = head;p;){
            if(p->random)   p->next->random = p->random->next;
            p = p->next->next;
        }

        auto dummy = new ListNode(-1);
        auto cur = dummy;

        for(auto p = head;p;){
            cur->next = p->next;
            cur = cur->next;
            p = p->next->next;
        }



        return dummy->next;


    }
};