138 随机链表的复制

https://leetcode.cn/leetbook/read/top-interview-questions-hard/xwbna3/

cost: 15m51s

/*
// 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) {
        Node dummy = Node(0);
        auto node = head;
        auto p = &dummy;
        unordered_map<Node*, Node*> nodes;
        while (node != nullptr) {
            if (!nodes.count(node)) {
                nodes[node] = new Node(node->val);
            }
            auto newNode = nodes[node];
            if (node->random != nullptr && !nodes.count(node->random)) {
                nodes[node->random] = new Node(node->random->val);
            }
            if (node->random) {
                newNode->random = nodes[node->random];
            }
            node = node->next;
            p->next = newNode;
            p = p->next;
        }
        return dummy.next;
    }
};