138. 随机链表的复制

难度：🟡 Medium | 标签：链表、哈希 | 状态：⬜ LeetCode 链接

思路

哈希法：第一遍按 next 复制节点，建立 老→新 映射；第二遍设置 random（查表）。

进阶：节点穿插法 O(1) 空间——把新节点插在老节点后，random 通过 old->random->next 取，最后拆开。

代码

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> mp;
        for (Node* p = head; p; p = p->next) mp[p] = new Node(p->val);
        for (Node* p = head; p; p = p->next) {
            mp[p]->next   = mp[p->next];
            mp[p]->random = mp[p->random];
        }
        return mp[head];
    }
};

复杂度

• 时间 O(n)，空间 O(n)（穿插法 O(1)）

易错 / 回顾

• 哈希默认值是 nullptr，所以 mp[nullptr] = nullptr 自动正确
• 穿插法精巧但易错，面试一般写哈希就够
• 一遍 DFS + 哈希也可