138. 随机链表的复制
3 min
题目
解法：哈希映射
思路
核心思想是使用哈希表建立原节点到新节点的映射关系。第一次遍历创建所有新节点并存入哈希表，第二次遍历通过映射设置新节点的next和random指针。
正确性在于：哈希表确保了每个原节点与新节点一一对应，当设置random指针时，通过原节点的random指针作为键，能直接定位到对应的新节点，从而保证新链表的指针关系与原链表完全一致。
- Step 1: 处理空链表特殊情况
- Step 2: 创建哈希表存储原节点到新节点的映射
- Step 3: 第一次遍历创建所有新节点并存入哈希表
- Step 4: 第二次遍历设置新节点的next和random指针
- Step 5: 返回新链表的头节点
复杂度
- 时间复杂度: ，两次线性遍历链表，哈希表操作均为
- 空间复杂度: ，哈希表存储所有节点的映射关系
代码
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == NULL) return NULL;
// 哈希表：原节点 -> 新节点
unordered_map<Node*, Node*> map;
// 第一次遍历：创建所有新节点
Node* cur = head;
while (cur != NULL) {
map[cur] = new Node(cur->val);
cur = cur->next;
}
// 第二次遍历：设置 next 和 random 指针
cur = head;
while (cur != NULL) {
map[cur]->next = map[cur->next];
map[cur]->random = map[cur->random];
cur = cur->next;
}
return map[head];
}
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == NULL) return NULL;
// 哈希表：原节点 -> 新节点
unordered_map<Node*, Node*> map;
// 第一次遍历：创建所有新节点
Node* cur = head;
while (cur != NULL) {
map[cur] = new Node(cur->val);
cur = cur->next;
}
// 第二次遍历：设置 next 和 random 指针
cur = head;
while (cur != NULL) {
map[cur]->next = map[cur->next];
map[cur]->random = map[cur->random];
cur = cur->next;
}
return map[head];
}
};