//Hashmap, copy node; then copy random;
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        unordered_map<RandomListNode*, RandomListNode*> old2new;
        RandomListNode* dummy = new RandomListNode(-1);
        RandomListNode* tmp = head;
        RandomListNode* curr = dummy;
        while (tmp) {
            RandomListNode* newNode = new RandomListNode(tmp->label);
            old2new[tmp] = newNode;
            curr->next = newNode;
            curr = curr -> next;
            tmp = tmp->next;
        }
        tmp = head;
        while (tmp) {
            //if (tmp->random) {
                old2new[tmp]->random = old2new[tmp->random];
            //}
            tmp = tmp-> next;
        }
        return dummy->next;
    }
};

/*第一遍扫的时候巧妙运用next指针， 开始数组是1->2->3->4  。 然后扫描过程中 先建立copy节点 1->1`->2->2`->3->3`->4->4`,
// 然后第二遍copy的时候去建立边的copy， 拆分节点, 一边扫描一边拆成两个链表，这里用到两个dummy node。
//第一个链表变回  1->2->3 , 然后第二变成 1`->2`->3`  */
//No HashMap version
public class Solution {
    private void copyNext(RandomListNode head) {
        while (head != null) {
            RandomListNode newNode = new RandomListNode(head.label);
            newNode.random = head.random;
            newNode.next = head.next;
            head.next = newNode;
            head = head.next.next;
        }
    }

    private void copyRandom(RandomListNode head) {
        while (head != null) {
            if (head.next.random != null) {
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
    }

    private RandomListNode splitList(RandomListNode head) {
        RandomListNode newHead = head.next;
        while (head != null) {
            RandomListNode temp = head.next;
            head.next = temp.next;
            head = head.next;
            if (temp.next != null) {
                temp.next = temp.next.next;
            }
        }
        return newHead;
    }

    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        copyNext(head);
        copyRandom(head);
        return splitList(head);
    }
}


/**
 * 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:
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    RandomListNode *copyRandomList(RandomListNode *head) {
        // write your code here
        if (head == NULL) {
            return NULL;
        }

        duplicateNodes(head);

        copyRandomNodes(head);

        return splitLists(head);
    }

    void duplicateNodes(RandomListNode *head) {
        RandomListNode* cur = head;
        while (cur != NULL) {
            cur = copyNodes(cur);
        }
        return;
    }

    RandomListNode* copyNodes(RandomListNode* cur) {
        RandomListNode* next = cur->next;
        RandomListNode* newNode = new RandomListNode(cur->label);
        cur->next = newNode;
        newNode->next = next;
        return next;
    }

    void copyRandomNodes(RandomListNode *head) {
        RandomListNode *cur = head;
        while (cur != NULL) {
            cur = setRandomNodes(cur);
        }
        return;
    }

    RandomListNode* setRandomNodes(RandomListNode* cur) {
        if (cur->random == NULL) {
            return cur->next->next;
        }
        RandomListNode* dupRandomNode = cur->random->next;
        cur->next->random = dupRandomNode;
        return cur->next->next;
    }

    RandomListNode* splitLists(RandomListNode* head) {
        RandomListNode* dummyOld = new RandomListNode(0);
        RandomListNode* dummyNew = new RandomListNode(0);
        dummyOld->next = dummyNew;
        dummyNew->next = head;
        RandomListNode* cur = dummyOld;

        while (cur != NULL) {
            cur = splitOnePair(cur);
        }

        return dummyNew->next;
    }

    RandomListNode* splitOnePair(RandomListNode* cur) {
        RandomListNode* next = cur->next->next;
        // Keep a pointer to the new node when splitting nodes;
        RandomListNode* newNode = cur->next;
        cur->next = next;
        // Need to validate if the next node is NULL; if it's NULL, there is NO next->next for the new nodes' next pointer to point to;
        if (next != NULL) {
            newNode->next = next->next;
        }
        return next;
    }
};