[LeetCode 138] 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.

Diffculty
Medium

Similar Problems
[LeetCode ] Clone Graph Medium

Analysis

这题的关键是如何track一个节点是否已经被 copy 了。假如我们要 copy 如下 list，用指针 p1 来扫描每个节点，另一个指针 p2 建立 copy。

| | | V 1 -> 2 -> 3

p1扫描1时，p2复制1，以及1->next (2), 1->random (3)。之后 p1, p2 分别移到各自的2节点。此时我们必须得知道节点3在之前已经被复制了，并且得知道复制节点的地址。

| | | V 1 -> 2 -> 3

所以这里可以使用一个hash table来记录原节点和复制节点的地址对应关系。这样每次要建立当前节点 p 的 next 和 random 前，先在 hash table 中查找。如果找到，则直接连接；否则建立新节点连上，并把和原节点的对应关系存入 hash table 中。

Solutions

class Solution { public: RandomListNode copyRandomList(RandomListNode head) { if (!head) return NULL; RandomListNode res = new RandomListNode(head->label); RandomListNode node = res; RandomListNode cur = head->next; map<RandomListNode, RandomListNode> m; m[head] = res; while (cur) { RandomListNode tmp = new RandomListNode(cur->label); node->next = tmp; m[cur] = tmp; node = node->next; cur = cur->next; } node = res; cur = head; while (node) { node->random = m[cur->random]; node = node->next; cur = cur->next; } return res; } };

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(!head) return NULL;
        unordered_map<RandomListNode*, RandomListNode*> ht;
        RandomListNode *p1 = head;
        RandomListNode *p2 = new RandomListNode(head->label);
        ht[head] = p2;
        while(p1) {
            if(p1->next) {
                if(ht.count(p1->next))
                    p2->next = ht[p1->next];
                else {
                    p2->next = new RandomListNode(p1->next->label);
                    ht[p1->next] = p2->next;
                }
            }
            if(p1->random) {
                if(ht.count(p1->random))
                    p2->random = ht[p1->random];
                else {
                    p2->random = new RandomListNode(p1->random->label);
                    ht[p1->random] = p2->random;
                }
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return ht[head];
    }
};