【C++习题】22.随机链表的复制

---

题目：138. 随机链表的复制 - 力扣（LeetCode）

链接🔗：138. 随机链表的复制 - 力扣（LeetCode）

题目：

---

代码：

class Solution {
public:// 函数功能：深拷贝带随机指针的链表// 参数：原链表的头节点指针// 返回值：拷贝后的新链表的头节点指针Node* copyRandomList(Node* head) {// 创建map用于存储原节点到拷贝节点的映射关系// key: 原链表节点地址// value: 对应的拷贝节点地址map<Node*, Node*> nodeMap;// copyhead指向拷贝链表的头节点// copytail指向拷贝链表的尾节点Node* copyhead = nullptr, *copytail = nullptr;// 第一次遍历：复制节点值和next指针Node* cur = head;while(cur){// 如果是第一个节点if(copytail == nullptr){// 创建头节点copyhead = copytail = new Node(cur->val);}else{// 创建新节点并连接到尾部copytail->next = new Node(cur->val);copytail = copytail->next;}// 建立原节点和拷贝节点的映射关系nodeMap[cur] = copytail;// 继续处理下一个节点cur = cur->next;}// 第二次遍历：处理random指针cur = head;          // cur指向原链表Node* copy = copyhead;  // copy指向拷贝链表while(cur){// 如果原节点的random为空if(cur->random == nullptr){copy->random = nullptr;}else{// 通过map找到原节点random指向的节点对应的拷贝节点copy->random = nodeMap[cur->random];}// 继续处理下一个节点cur = cur->next;copy = copy->next;}return copyhead;}
};

算法思路解析：

1. 整体思路：
   • 分两次遍历完成深拷贝
   • 第一次遍历复制节点值和next指针，同时建立映射关系
   • 第二次遍历处理random指针
2. 具体步骤：
   • 第一次遍历：
     • 复制每个节点的值
     • 建立next连接
     • 将原节点和对应的拷贝节点存入map
   • 第二次遍历：
     • 根据原节点的random指向
     • 通过map找到对应的拷贝节点
     • 建立random连接
3. 时间复杂度：
   • O(N)，需要两次遍历链表
   • map的插入和查找操作是O(logN)
4. 空间复杂度：
   • O(N)，需要额外的map存储映射关系