LeetCode | Copy List with Random Pointer

https://leetcode.com/problems/copy-list-with-random-pointer/

思路1：先拷贝整个链表，不考虑random域，同时用一个hash map存下原链表节点和复制节点的对应关系。然后再遍历一次原链表，构造新链表的random域。需要O(n)的额外空间。

/**
 * 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:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if (!head) return NULL;
        unordered_map<RandomListNode*, RandomListNode*> map;
        RandomListNode dummy(0), *cur = &dummy, *p = head;
        while (p) {
            cur->next = new RandomListNode(p->label);
            map[p] = cur->next;
            p = p->next;
            cur = cur->next;
        }
        p = head; cur = dummy.next;
        while (p) {
            cur->random = map[p->random];
            p = p->next;
            cur = cur->next;
        }
        return dummy.next;
    }
};

思路2：复制的时候按这样的连接关系：1->1'->2->2'->3->3'...（x'表示节点x的复制节点），即把新节点插入原链表中。这么做的好处是用x->next就是复制节点，x->next->next就是原链表中的下一个节点，既保存了对应关系，又不需要额外的空间。最后再将链表拆开即可。

该方法写起来其实不容易。而且没有通用性，记住有这么个巧妙的做法就好。

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if (!head) return NULL;
        
        // construct a list like 1->1'->2->2'...
        RandomListNode *cur = head;
        while (cur) {
            RandomListNode *next = cur->next;
            cur->next = new RandomListNode(cur->label);
            cur->next->next = next;
            cur = next;
        }
        
        // copy the random pointer
        cur = head;
        while (cur) {
            RandomListNode *next = cur->next->next;
            if (cur->random) cur->next->random = cur->random->next;  // 判断是必要的
            cur = next;
        }
        
        // split the list
        RandomListNode *ori = head, *cop = head->next, *ret = head->next;
        while (ori) {
            ori->next = ori->next->next;
            if (cop->next) cop->next = cop->next->next;
            ori = ori->next;
            cop = cop->next;
        }

        return ret;
    }
};