138. Copy List with Random Pointer

題目: 138. Copy List with Random Pointer

題目描述

給定一個鏈結串列，其中每個節點除了有一個 next 指標外，還有一個額外的指標 random，該指標可以指向鏈結串列中的任意節點或是 null。

請實作一個函式，對這個鏈結串列進行深度複製（Deep Copy），返回新的鏈結串列的頭節點。

限制條件

• 0 <= n <= 1000
• -10^4 <= Node.val <= 10^4
• Node.random 為 null 或指向鏈結串列中的某個節點

解題思路

要深度複製這個鏈結串列，同時處理 next 和 random 指標，我們可以採取以下方法：

方法一：使用雜湊表

• 步驟：
  1. 第一遍遍歷：創建一個映射，將原始節點與新複製的節點對應起來。
  2. 第二遍遍歷：根據映射，更新新節點的 next 和 random 指標。
• 缺點：需要額外的空間來存儲映射，空間複雜度為 O(n)。

方法二：在原地進行複製（最佳解）

為了實現在 O(n) 時間和 O(1) 空間複雜度下完成深度複製，我們可以：

1. 第一遍遍歷：
   • 對於每個原始節點 node，創建一個新的節點 copy，將其插入到 node 之後。
   • 這樣，鏈結串列的結構將變為：node1 -> copy1 -> node2 -> copy2 -> ...。
2. 第二遍遍歷：
   • 更新新節點的 random 指標：
     • copy.random = node.random ? node.random.next : nullptr;
   • 因為 node.random.next 是 node 的隨機指向節點的複製節點。
3. 第三遍遍歷：
   • 將新節點從原始鏈結串列中分離出來，恢復原始鏈結串列，並得到複製的鏈結串列。

程式碼

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) {
            return nullptr;
        }

        // 自我複製
        auto node = head;
        while (node) {
            auto nextNode = node->next;
            node->next = new Node(node->val, nextNode);
            node = nextNode;
        }

        // 假設 node1->random 為 node2
        // 則 copy1->random 為 copy2
        // 又 node1->next == copy1 && node2->next == copy2
        // node1->next->random == node2->next
        // node1->next->random == node1->random->next
        node = head;
        while (node) {
            node->next->random = node->random ? node->random->next : nullptr;
            node = node->next->next;
        }

        // 將偶數位的node組成複製的 list
        auto dummy = new Node(0);
        auto copy = dummy;
        node = head;
        while (node) {
            auto nextNode = node->next->next;
            copy->next = node->next;
            node->next = node->next->next;

            copy = copy->next;
            node = node->next;
        }

        return dummy->next;
    }
};

時間與空間複雜度分析

• 時間複雜度：O(n)
  • 分析：我們總共遍歷了鏈結串列三次，每次的操作都是 O(n)，因此總的時間複雜度為 O(n)。
• 空間複雜度：O(1)
  • 分析：我們在原地進行操作，除了少量的指標變數和新創建的節點外，沒有使用額外的空間，符合常數級別的空間複雜度要求。