138. 随机链表的复制 - 题解与详细分析

题目描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

示例

示例 1：

text

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

text

输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]

示例 3：

text

输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]

解题思路

这道题的关键在于如何处理随机指针。由于随机指针可能指向链表中的任意节点，简单的遍历复制无法处理随机指针的指向问题。

核心思想：三步法

1. 插入复制节点：在原链表的每个节点后面插入一个复制节点
2. 设置随机指针：根据原节点的随机指针设置复制节点的随机指针
3. 分离链表：将原链表和复制链表分离

这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)（不包括结果链表）。

代码实现

c

/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ // 创建新节点函数 struct Node* BuyNode(int x) { struct Node* NewNode = (struct Node*)malloc(sizeof(struct Node)); NewNode->val = x; NewNode->next = NULL; NewNode->random = NULL; return NewNode; } struct Node* copyRandomList(struct Node* head) { if (head == NULL) return NULL; struct Node* cur = head; // 第一步：在原链表的每个节点后面拷贝一个节点 while(cur) { struct Node* next = cur->next; struct Node* newnode = BuyNode(cur->val); newnode->next = next; cur->next = newnode; cur = next; } // 第二步：设置random指针 cur = head; while(cur) { if(cur->random == NULL) { cur->next->random = NULL; } else { cur->next->random = cur->random->next; } cur = cur->next->next; } // 第三步：将新链表和旧链表断开，并各自链接 cur = head; struct Node* newhead = NULL; struct Node* newtail = NULL; while(cur) { // 将copy节点标记下来 struct Node* temp = cur->next; // 去掉copy节点，然后恢复原链表 cur->next = temp->next; if(newhead == NULL) { newhead = temp; newtail = temp; } else { newtail->next = temp; newtail = newtail->next; } cur = temp->next; } return newhead; }

代码详解

第一步：插入复制节点

c

while(cur) { struct Node* next = cur->next; struct Node* newnode = BuyNode(cur->val); newnode->next = next; cur->next = newnode; cur = next; }

执行效果：

text

原链表：A → B → C → NULL 插入后：A → A' → B → B' → C → C' → NULL

关键点：

• 在每个原节点后面插入一个复制节点
• 复制节点的值与原节点相同
• 保持链表的连接关系

第二步：设置随机指针

c

while(cur) { if(cur->random == NULL) { cur->next->random = NULL; } else { cur->next->random = cur->random->next; } cur = cur->next->next; }

关键点：

• 如果原节点的random为NULL，复制节点的random也为NULL
• 如果原节点的random不为NULL，复制节点的random指向原节点random指向的节点的下一个节点（即对应的复制节点）
• 因为每个原节点后面都跟着它的复制节点，所以 cur->random->next 就是原节点random指向的节点的复制节点

第三步：分离链表

c

while(cur) { struct Node* temp = cur->next; // 复制节点 cur->next = temp->next; // 恢复原链表 if(newhead == NULL) { newhead = temp; newtail = temp; } else { newtail->next = temp; newtail = newtail->next; } cur = temp->next; // 移动到下一个原节点 }

关键点：

• 将复制节点从原链表中分离出来
• 恢复原链表的next指针
• 构建新的复制链表

执行过程可视化

以示例1为例：

原链表：

text

节点0: 7 -> random: NULL 节点1: 13 -> random: 节点0 节点2: 11 -> random: 节点4 节点3: 10 -> random: 节点2 节点4: 1 -> random: 节点0

第一步后：

text

7 → 7' → 13 → 13' → 11 → 11' → 10 → 10' → 1 → 1' → NULL

第二步后（设置random）：

• 7'.random = NULL
• 13'.random = 7'
• 11'.random = 1'
• 10'.random = 11'
• 1'.random = 7'

第三步后（分离）：

• 原链表恢复：7 → 13 → 11 → 10 → 1 → NULL
• 复制链表：7' → 13' → 11' → 10' → 1' → NULL

复杂度分析

• 时间复杂度：O(n)，需要遍历链表三次
• 空间复杂度：O(1)，不包括结果链表，只使用常数级别的额外空间

其他解法

方法二：哈希表法

c

struct Node* copyRandomList(struct Node* head) { if (head == NULL) return NULL; // 创建哈希表，映射原节点到复制节点 struct Node* hash[1000] = {0}; int index = 0; // 第一次遍历：创建所有节点并建立映射 struct Node* cur = head; while (cur != NULL) { hash[index] = BuyNode(cur->val); cur = cur->next; index++; } // 第二次遍历：设置next和random指针 cur = head; index = 0; while (cur != NULL) { if (cur->next != NULL) { hash[index]->next = hash[index + 1]; } if (cur->random != NULL) { // 找到random指向的节点在链表中的位置 struct Node* temp = head; int random_index = 0; while (temp != cur->random) { temp = temp->next; random_index++; } hash[index]->random = hash[random_index]; } cur = cur->next; index++; } return hash[0]; }

优缺点：

• 优点：思路简单直观
• 缺点：需要 O(n) 的额外空间，且寻找random索引需要 O(n) 时间

关键点总结

1. 插入复制节点：这是处理随机指针的关键，使得每个原节点后面都跟着它的复制节点
2. 随机指针设置：利用 cur->random->next 找到对应的复制节点
3. 链表分离：仔细处理指针，确保原链表恢复，复制链表正确连接
4. 边界情况：处理空链表、单个节点等情况

扩展思考

如果链表有环怎么办？

如果原链表有环，这种方法仍然有效，因为：

1. 插入复制节点后，环的大小会翻倍
2. 设置随机指针时，逻辑不变
3. 分离链表时，仍然可以正确分离

如果要求不修改原链表？

可以使用哈希表法，但空间复杂度会变为 O(n)。

应用场景

这种深拷贝带有随机指针的链表在以下场景中有应用：

1. 对象序列化：深度复制复杂对象结构
2. 图算法：复制带有随机边的图结构
3. 数据库：复制关联数据结构
4. 游戏开发：复制游戏对象及其关联关系

总结

随机链表的复制是一个经典的链表问题，考察了对指针操作和链表结构的深入理解：

1. 核心技巧：三步法（插入→设置随机指针→分离）
2. 关键洞察：通过在原节点后插入复制节点，可以轻松找到对应的随机指针目标
3. 指针操作：需要仔细处理指针，避免内存泄漏或指针错误
4. 效率优化：O(n) 时间复杂度和 O(1) 空间复杂度（不包括结果）

掌握这种解法对于处理复杂的链表结构和指针操作非常有帮助。