AcWing 48. 复杂链表的复刻
原题链接
中等
作者:
欧浩辰我宣你
,
2023-03-23 10:06:09
,
所有人可见
,
阅读 104
/**
* Definition for singly-linked list with a random pointer.
* struct ListNode {
* int val;
* ListNode *next, *random;
* ListNode(int x) : val(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
ListNode *copyRandomList(ListNode *head) {
unordered_map<ListNode*, ListNode*> hash;
hash[nullptr] = nullptr;
auto dup = new ListNode(-1), dup_head = 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);
dup_head->next = hash[head];
dup_head->next->random = hash[head->random];
dup_head = dup_head->next;
head = head->next;
}
return dup->next;
}
};