Copy List with Random Pointer

题目：

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

分析：

用hashing的方法可以一次做对，印象还有一点，分析一下可以知道hash的方式应该是old to new，因为old结点可以通过对应的下标找到，然后hash告诉我们他对应的new结点是什么，然后random指过去。

方法2用的是O(1)的空间复杂度，操作会多一点，看如何取舍了。方法2的三步骤为，copyNext, copyRandom, splitList。

解法1：

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;
        }

        unordered_map<RandomListNode*, RandomListNode*> hash;
        RandomListNode* curr = head;

        RandomListNode dummy(0);
        RandomListNode* newList = &dummy;

        while (curr != NULL) {
            // copy
            RandomListNode* temp = new RandomListNode(curr->label);
            newList->next = temp;
            // hash (hash is from old to new)
            hash[curr] = temp;
            // move pointer
            newList = newList->next;
            curr = curr->next;
        }

        curr = head;
        newList = dummy.next;

        while (newList != NULL) {
            newList->random = hash[curr->random];
            curr = curr->next;
            newList = newList->next;
        }

        return dummy.next;
    }
};

解法2：

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.
     */

    void copyNext(RandomListNode* head) {
        RandomListNode* curr = head;
        while (curr != NULL) {
            RandomListNode* temp = new RandomListNode(curr->label);
            temp->next = curr->next;
            curr->next = temp;
            curr = curr->next->next;
        }
    } 

    void copyRandom(RandomListNode* head) {
        RandomListNode* curr = head;
        while (curr != NULL) {
            if (curr->random != NULL) {
                curr->next->random = curr->random->next;
            }
            curr = curr->next->next;
        }
    }


    RandomListNode* splitList(RandomListNode* head) {
        RandomListNode dummy(-1);
        RandomListNode* curr = &dummy;
        while (head != NULL) {
            curr->next = head->next;
            curr = curr->next;
            head->next = curr->next;
            head = head->next;
        }
        return dummy.next;
    }

    RandomListNode *copyRandomList(RandomListNode *head) {
        // write your code here
        if (head == NULL) {
            return NULL;
        }

        copyNext(head);
        copyRandom(head);
        RandomListNode* res = splitList(head);
        return res;
    }
};