目录
- 一、题目描述
- 示例1：
- 示例2：
- 示例3：
- 示例4：
- 二、思路分析
- 三、整体代码
- 总结
一、题目描述
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例4：
输入：head = []
输出：[]解释：给定的链表为空（空指针），因此返回 null。
提示：
-10000 <= Node.val <= 10000
Node.random 为空(null)或指向链表中的节点。
节点数目不超过 1000 。
二、思路分析
注：思路分析中的一些内容和图片参考自力扣各位前辈的题解，感谢他们的无私奉献
分析
复制普通链表：给定链表的头结点head，复制普通链表很简单，只需遍历链表，每轮需要：建立新结点 + 让前驱结点的next指向当前这个新结点 + 让当前这个新结点的next指向空
复制复杂链表：本题链表的结点新增了 random 指针，指向链表中的任意结点或者null。这个 random 指针意味着在复制过程中，除了构建前驱结点的next指针，还要构建前驱结点的ramdom指针。因此，每轮需要：建立2个新结点 + 让前驱结点的next指向第1个新结点 + 让前驱结点的random指向第2个新结点。但是这有一个问题：并不是每次都需要建立2个新结点。有时候前驱结点的random指向的是已经存在的结点，但是如何判断出来呢？如果把所有结点遍历一遍，那就太麻烦了。
思路
利用哈希表的查询特点，考虑构建原链表结点和新链表对应结点的键值对映射关系，再遍历构建新链表各结点的next和random引用指向即可。
算法流程：
①若头节点head为空结点，直接返回NULL ；
②初始化：声明一个哈希表dic，定义一个结点cur指向头结点，这个cur控制后面的循环
③建立哈希映射：遍历这个链表，每个链表结点对应建立一个新结点，并向dic添加键值对(原cur结点, 新cur结点)
④构建新链表的引用指向：构建新结点的next和random引用指向
⑤返回值： 返回新链表的头结点，即dic[cur]
三、整体代码
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
//若是空链表，则返回NULL
if(head == NULL) return NULL;
//创建一个结点，指向这个链表的头结点。这个结点用来控制后面的循环
Node* cur = head;
//创建一个哈希表
unordered_map<Node*, Node*> map;
while(cur != NULL){
//为链表每个结点创建一个对应的新结点，并建立原结点和新结点的Map映射
map[cur] = new Node(cur->val);
cur = cur->next;
}
cur = head;
//为新链表每个结点的next和random设置对应的指向
while(cur != NULL){
map[cur]->next = map[cur->next];
map[cur]->random = map[cur->random];
cur = cur->next;
}
//返回新链表的头结点
return map[head];
}
};
总结
本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注的更多内容!
评论(0)