題目網址：https://leetcode.cn/problems/copy-list-with-random-pointer/

題意：給一長度為 n 的 linked list, 每個節點包含一個額外增加的隨機 pointer random, 該 pointer 可以指向 linked list 中的任何節點 or 空節點。

建構該 linked list 的 deep copy, 它由 n 個新節點組成, 其中每個新節點的值都設為其對應的 node.val。

新節點的 next 和 random 也都應指向新 linked list 中的其他節點, 使原 linked list 和新 linked list 能夠表示成相同的 linked list。

e.g. 如果原 linked list 中有 X 和 Y 兩個節點, 其中 X.random --> Y。則新 linked list 中對應的兩個節點 x 和 y, 同樣有 x.random --> y。

返回新 linked list 的 head。

Solution 1：

想法：利用 hash table, 先遍歷原 linked list, 並在遍歷的同時不斷創建新節點, 將 原節點 作為 key、新節點 作為 value 放入 hash table 中。最後, 再遍歷一次原 linked list, 並設置新 linked list 的 next 和 random

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node *cur = head;
        unordered_map<Node*, Node*> oldToNew; // {old, new}

        while (cur) {
            Node *newNode = new Node(cur->val);
            oldToNew[cur] = newNode;
            cur = cur->next;
        }

        cur = head;
        while (cur) {
            oldToNew[cur]->next = oldToNew[cur->next];
            oldToNew[cur]->random = oldToNew[cur->random];
            cur = cur->next;
        }
        return oldToNew[head];
    }
};
  • time：$O(n)$ ➔ 遍歷 linked list
  • space：$O(n)$ ➔ oldToNew

Solution 2：

想法：分成三個步驟

  • 根據遍歷到的原節點來創建對應的新節點, 並把每個新節點放在原節點後面
    e.g. 1 -> 1' -> 2 -> 2' -> 3 -> 3'
  • 設置新節點的 random
    ➔ 新節點的 random 為原節點的 random->next (原 random 對應的新節點)
  • 將兩個 linked list 分開
class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 根據遍歷到的原節點來創建對應的新節點, 並把每個新節點放在原節點後面
        Node *cur = head;
        while (cur) {
            Node *newNode = new Node(cur->val);
            newNode->next = cur->next;
            cur->next = newNode;
            cur = newNode->next;
        }

        // 設置新節點的 random
        cur = head;
        while (cur) {
            // 不用判斷 cur->next 是否為 null, 是因為 cur 為原 linked list 的節點
            // cur->next 為對應的新節點, 在 cur != null 的前提下, cur->next 必不為 null
            if (cur->random) {
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }

        // 將兩個 linked list 分開
        cur = head;
        Node *dummy = new Node(0), *tail = dummy;
        while (cur) {
            tail->next = cur->next; // 將新節點加到新 linked list
            tail = tail->next; // 更新 tail
            cur->next = tail->next; // 將 cur 指向下一個原 linked list 的 node
            cur = cur->next; // 將 cur 更新成下一個原 linked list 的 node
        }
        return dummy->next;
    }
};
  • time：$O(n)$ ➔ 遍歷 linked list
  • space：$O(1)$ ➔ 若不考慮要 copy 的 node, 只需常數空間