138. 复制带随机指针的链表：用哈希表建立新旧节点映射

链表中的每个节点除了 next 指针外，还包含一个 random 指针。random 可以指向链表中的任意节点，也可以为空。题目要求创建一份完全独立的深拷贝：新链表中的节点值相同，但所有指针都必须指向新节点，不能引用原链表。

思路：分两次遍历#

关键是维护一张“旧节点 $→$ 新节点”的映射表 m，并将复制过程拆成两个阶段：

第一次遍历只复制节点本身，将每个旧节点和对应的新节点写入 m。
第二次遍历根据映射表设置新节点的 next 和 random 指针。

这样，即使 random 指向后面的节点，也可以直接通过映射表找到对应的新节点；如果指针为空，map 对应的值也为空，不会把原节点带入深拷贝。

为什么不能只复制 next
如果在创建节点时直接复制 random，得到的指针仍然属于原链表。必须先保证所有新节点都已经创建，再统一连接指针。

1
/*
2
// Definition for a Node.
3
class Node {
4
public:
5
    int val;
6
    Node* next;
7
    Node* random;
8

9
    Node(int _val) {
10
        val = _val;
11
        next = NULL;
12
        random = NULL;
13
    }
14
};
15
*/
16

17
class Solution {
18
public:
19
    typedef struct Node* PtrToNode;
20
    Node* copyRandomList(Node* head) {
21
        if(head == NULL) return NULL;
22

23
        map<PtrToNode, PtrToNode> m;
24

25
        PtrToNode cur = head;
26
        while(cur != NULL) {
27
            m[cur] = new Node(cur->val);
28
            cur = cur->next;
29
        }
30

31
        cur = head;
32
        while(cur != NULL) {
33
            m[cur]->next = m[cur->next];
34
            m[cur]->random = m[cur->random];
35

36
            cur = cur->next;
37
        }
38

39
        return m[head];
40
    }
41
};

复杂度与边界#

时间复杂度： $O(n)$ ，两次遍历链表，映射查询的复杂度取决于 map 的实现。
空间复杂度： $O(n)$ ，映射表保存每个旧节点对应的新节点。
空链表直接返回 NULL。
random 为空时，m[cur->random] 对应空指针；random 指向自身或其他任意节点时，都能通过映射表正确连接。

题目链接：复制带随机指针的链表