题目链接

第一次遇到的时候这个题目的思路让我眼前一亮…

代码极度简单——

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> mp;
        Node* cur = head;

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

        cur = head;

        while(cur!=nullptr){
            mp[cur]->next = mp[cur->next];
            mp[cur]->random = mp[cur->random];
            cur = cur->next;
        }

        return mp[head];

    }
};

核心之处在于巧妙地利用了映射，把旧地址和新地址联系在一起。这样就不用管其他具体的random是什么next是什么了！

或许链表的题目就是需要把一个个 Node 看成一个个整体，next指针看成一个连接 Nodes 的箭头？