LeetCode 138. Copy List with Random Pointer [Medium] [C++] 解題筆記

 這題給我們一個 Linked List 的串列，要我們照 deep copy 的方式將它複製一份。

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: The given linked list is empty (null pointer), so return null.

想法:

    其實這題想考察的就是大家對於 deep copy 以及 shallow copy 的了解，簡單說 shallow copy 就是只複製

指標本身，對其指向的內容並不做複製，也就是說只是多一個指標變數指向同一個記憶體位置，而 deep copy 則是連同原本

指標指向的記憶體位置的內容一併複製，等於新增一個指標變數並且新增一個記憶體空間存放與原本指標指向的內容完全一樣的資料。

完整程式碼:

/*
// 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) {
        unordered_map<Node*, Node*> m;
        Node* cur = head;
        while (cur != nullptr) {
            if (!m.count(cur)) {
                m[cur] = new Node(cur->val);
            }
            if (!m.count(cur->next)) {
                m[cur->next] = (cur->next)? new Node(cur->next->val) : nullptr;
            }
            if (!m.count(cur->random)) {
                m[cur->random] = (cur->random)? new Node(cur->random->val) : nullptr;
            }
            Node* copied = m[cur];
            copied->next = m[cur->next];
            copied->random = m[cur->random];
            cur = cur->next;
        }
        return m[head];
    }
};