# 138 - Copy List with Random Pointer

解法一 - 用 hash table 存原本 list 跟新 list 之間的對應關係

我們可以先走過一次原本的 list，先複製所有的 node 跟 next，並且把舊 node 跟新 node 之間的對應關係儲存起來。

img

這個方法比較直觀，但缺點是會多花 O(n) 的記憶體空間。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return NULL;

        Node* newHead = new Node(0);
        Node* ptr = newHead;

        map<Node*, Node*> table;

        Node* itr = head;
        while(itr) {
            ptr->next = new Node(itr->val);
            ptr->next->next = itr->next;

            table.insert(pair<Node*, Node*>(itr, ptr->next) );

            itr = itr->next;
            ptr = ptr->next;
        }

        itr = head;
        while(itr) {
            table[itr]->random = table[itr->random];
            itr = itr->next;
        }

        return newHead->next;
    }
};

/*pseudo code:
create a map<Node*, Node*>

create new head & ptr
go through the old list
   copy all nodes' value and next to the new list
   store the old node and new node pair to map

go through the old list
   set the corresponding new node's random to old node's random's new node

return new head
*/

實際跑起來的時間如下：

Runtime: 32 ms, faster than 93.26% of C++ online submissions for Copy List with Random Pointer. Memory Usage: 22.3 MB, less than 16.81% of C++ online submissions for Copy List with Random Pointer.

解法二 - 每個 node 都先複製一份，再分離出來

這個解法滿聰明的，主要是希望在每個 node 後面複製一份同樣的 node，這樣就不需要像解法一用額外的空間去存 old list node 跟 new list node 之間的對應關係。

img

原始連結在這邊：https://leetcode.com/problems/copy-list-with-random-pointer/discuss/43491/A-solution-with-constant-space-complexity-O(1)-and-linear-time-complexity-O(N)

C++ 的實作如下：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node *newHead, *l1, *l2;
        if (head == NULL) return NULL;

        // Copy each node and connect to original node
        for (l1 = head; l1 != NULL; l1 = l1->next->next) {
            l2 = new Node(l1->val);
            l2->next = l1->next;
            l1->next = l2;
        }

        // Copy random pointer
        newHead = head->next;
        for (l1 = head; l1 != NULL; l1 = l1->next->next) {
            if (l1->random != NULL) l1->next->random = l1->random->next;
            else l1->next->random = NULL;
        }

        // Seperate the copied list
        for (l1 = head; l1 != NULL; l1 = l1->next) {
            l2 = l1->next;
            l1->next = l2->next;
            if (l2->next != NULL) l2->next = l2->next->next;
        }

        return newHead;
    }
};

時間如下：

Runtime: 36 ms, faster than 82.83% of C++ online submissions for Copy List with Random Pointer. Memory Usage: 22.2 MB, less than 29.43% of C++ online submissions for Copy List with Random Pointer.

Reference

• Leetcode 的 Solution