138. Copy List with Random Pointer

138. Copy List with Random Pointer

題意

給定一個 linked list，但這個 linked list 除了 next 之外有額外的指標 random 指向隨機的 list 中的節點

題目要求 deep copy 這個 linked list

限制

• 0 <= n <= 1000

• -104 <= Node.val <= 104

• Node.random is null or is pointing to some node in the linked list.

思考

• 利用兩個 map 存下原本的 list 與複製後的 list 的所有 reference 與位置

  • 遍歷 list 之後儲存所需資訊

    • 原本的 list ⇒ unordered_map<Node*, int> origin

    • 複製的 list => unordered_map<int, Node*> copied

  • 從頭開始再一次遍歷原本的 list，同時平行的遍歷複製的 list

    • 對每個原 list 的節點 node ，複製的節點 copy

    • copy→random = copied[origin[node→random]]

    • node = node→next; copy = copy→next;

  • Space Complexity: O(n)

• 可以不需要額外記憶體達成複製，參考解答

  • 將 linked list 的每個節點都複製之後接在原節點後方

    • 1 → 2 → 3 ⇒ 1 → 1’ → 2 → 2’ → 3 → 3’

  • 會形成這個效果

    • node1’→random == node1→random→next

  • 同時 node1→next == node1’

  • 經過上述的辦法將複製出來的節點 random 都指向正確的位置後，再將複製的節點 (list 中的偶數位節點都是複製的) 移除並組成新的 list

  • 如此一來不需要額外的空間，Space complexity為 O(1)

Solution

/*
// 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;
    }
};