青岛开发区建网站公司,网站查询网,半成品公司 网站,深互动平台怎么使用文章目录 题目#xff1a;138. 随机链表的复制 - 力扣#xff08;LeetCode#xff09;代码#xff1a; 题目#xff1a;138. 随机链表的复制 - 力扣#xff08;LeetCode#xff09;
链接#x1f517;#xff1a;138. 随机链表的复制 - 力扣#xff08;LeetCode… 文章目录 题目138. 随机链表的复制 - 力扣LeetCode代码 题目138. 随机链表的复制 - 力扣LeetCode
链接138. 随机链表的复制 - 力扣LeetCode
题目 代码
class Solution {
public:// 函数功能深拷贝带随机指针的链表// 参数原链表的头节点指针// 返回值拷贝后的新链表的头节点指针Node* copyRandomList(Node* head) {// 创建map用于存储原节点到拷贝节点的映射关系// key: 原链表节点地址// value: 对应的拷贝节点地址mapNode*, 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;}
};算法思路解析 整体思路 分两次遍历完成深拷贝第一次遍历复制节点值和next指针同时建立映射关系第二次遍历处理random指针 具体步骤 第一次遍历 复制每个节点的值建立next连接将原节点和对应的拷贝节点存入map 第二次遍历 根据原节点的random指向通过map找到对应的拷贝节点建立random连接 时间复杂度 O(N)需要两次遍历链表map的插入和查找操作是O(logN) 空间复杂度 O(N)需要额外的map存储映射关系
