Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 138. Copy List with Random Pointer

---

題目：


解答：

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

        Node *cur = head;
        unordered_map<Node*, Node*> q;

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

        cur = head;
        while (cur) {
            q[cur]->next = q[cur->next];
            q[cur]->random = q[cur->random];
            cur = cur->next;
        }

        return q[head];
    }
};