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;
        Node *curr = head;

        // Generate copy node and link it to list.
        while(curr){
            Node *dummy = new Node(curr->val);
            dummy->next = curr->next;
            curr->next = dummy;
            curr = dummy->next;
        }

        // Set random ptr of copy node.
        curr = head;
        while(curr){
            curr->next->random = (curr->random) ? curr->random->next : NULL;
            curr = curr->next->next;
        }

        // Separate the list and return.
        Node *newHead = head->next;
        curr = head;
        while(curr){
            Node* tmp = curr->next->next;
            curr->next->next = (tmp) ? tmp->next: NULL;
            curr->next = tmp;
            curr = tmp;
        }
        return newHead;
    }
};