题目描述
blablabla
样例
blablabla
一遍循环,思路清晰
$O(n)$
使用hash存储 key = 源链表节点,value = 目标链表节点,遍历源链表,判断每个节点和random节点是否在hash表中,如果不存在则创建
C++ 代码
class Solution {
public:
ListNode *copyRandomList(ListNode *head) {
unordered_map<ListNode*, ListNode*> hash;
hash[nullptr] = nullptr;
auto dup = new ListNode(-1), tail = dup;
while(head)
{
if(!hash.count(head)) hash[head] = new ListNode(head->val);
if(!hash.count(head->random)) hash[head->random] = new ListNode(head->random->val);
tail->next = hash[head];
tail->next->random = hash[head->random];
tail = tail->next;
head = head->next;
}
return dup->next;
}
};
想请问一下 为什么会出现hash.count(head) !=0 的情况呢
当前的head有可能是前面结点的random,在之前已经创建了新结点,并加入到hash中了;若再创建就是2个不同的点了
tql
问:我这个代码哪里有问题?
牛!!
如果每次都新创建一个,这样是不是存在原本两个点的random指向的是一个点,现在每次都新创建导致指向的是两个点呢?
哈希表运用的炉火纯青 赞
清晰
666
妙 啊!
6666