138. 複製隨機鏈表

思路

要複製鏈表，但是不只有一個指針，題目還包含了隨機亂指的指針。
我們需要讓隨機部分一併複製過去，所以得用個方法知道「複製後的節點」的位置。
因此，在第一次遍歷時，將複製的節點插入在原有節點之間。 也就是 $\begin{bmatrix} 1, 2, 3,\dots \end{bmatrix} \to \begin{bmatrix} 1,\blue{1'},2, \blue{2'}, 3, \blue{3'} \end{bmatrix}$，這樣在複製隨機部份時，就能得知複製後的節點位置了。

• 程式碼當中的temp是當前節點curr的下一個節點。

程式碼

鏈表（妙！）

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

        // 1. 複製 next 節點
        Node *curr = head, *temp = nullptr;
        while(curr != nullptr) {
            temp = curr -> next;
            curr -> next = new Node(curr -> val);
            curr -> next -> next = temp;
            curr = temp;
        }
        // 2. 複製 random 節點
        curr = head;
        while(curr != nullptr) {
            temp = curr -> next; // 複製的節點
            if(curr -> random != nullptr) {
                temp -> random = curr -> random -> next; // 將複製節點的 random 相連
            }            
            curr = temp -> next;
        }
        // 3. 分離複製的節點
        curr = head;
        Node* dummy = new Node(0);
        dummy -> next = curr -> next;

        while(curr != nullptr) {
            temp = curr -> next;
            curr -> next = temp -> next;
            curr = curr -> next;
            if(curr != nullptr) {
                temp -> next = curr -> next;
                temp = temp -> next;
            }
        }
        return dummy -> next;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$