138. Copy List with Random Pointer (Hard)

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.

Solution 1: Hash Table

这道链表的深度拷贝题的难点就在于如何处理随机指针的问题，由于每一个节点都有一个随机指针，这个指针可以为空，也可以指向链表的任意一个节点，如果我们在每生成一个新节点给其随机指针赋值时，都要去便利原链表的话，OJ上肯定会超时，所以我们可以考虑用Hash map来缩短查找时间，第一遍遍历生成所有新节点时同时建立一个原节点和新节点的哈希表，第二遍给随机指针赋值时，查找时间是常数级。代码如下：

version 1: 152ms

loop一遍，把random跟next都创建好

/**
 * 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;
        map<RandomListNode *, RandomListNode *> m;
        RandomListNode *res = new RandomListNode(head->label);
        RandomListNode *cur = res;
        while (head) {
            if (head->next) {
                if (m.find(head->next) == m.end()) {
                    RandomListNode *tmp = new RandomListNode(head->next->label);
                    m[head->next] = tmp;
                }
                cur->next = m[head->next];
            }

            if (head->random) {
                if (m.find(head->random) == m.end()) {
                    RandomListNode *tmp = new RandomListNode(head->random->label);
                    m[head->random] = tmp;
                }
                cur->random = m[head->random];
            }

            head = head->next;
            cur = cur->next;
        }

        return res;
    }
};

version 2: 59ms

先loop一遍next，把每个点都创建好，存入map 第二遍loop，从map里找random在map里存的值

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        unordered_map<RandomListNode*, RandomListNode*> m;
        RandomListNode* node = head;
        while (node) {
            m[node] = new RandomListNode(node->label);
            node = node->next;
        }

        node = head;
        while (node) {
            m[node]->next = m[node->next];
            m[node]->random = m[node->random];
            node = node->next;
        }
        return m[head];
    }
};

Solution 2: save space 56ms

The algorithm is composed of the follow three steps which are also 3 iteration rounds.

1. Iterate the original list and duplicate each node. The duplicate of each node follows its original immediately.
2. Iterate the new list and assign the random pointer for each duplicated node.
3. Restore the original list and extract the duplicated nodes.

/**
 * 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) {
        RandomListNode *cur = head;
        // insert coped nodes right after original nodes
        while (cur) {
            RandomListNode *tmp = new RandomListNode(cur->label);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = tmp->next;
        }

        // add random nodes to coped nodes
        cur = head;
        while (cur) {
            if (cur->random) cur->next->random = cur->random->next;
            cur = cur->next->next;
        }

        // decouple to two list
        cur = head;
        RandomListNode* res = head ? head->next:NULL;
        while (cur) {
            RandomListNode* tmp = cur->next; // current copied node
            cur->next = tmp->next; // ori list: link to next original node
            if (tmp->next) {
                tmp->next = cur->next->next; // copy list:link to next copied node
            }
            cur = cur->next; // update to next original node
        }
        return res;
    }
};