暴力做法
时间复杂度 O (n^2)
- 遍历一遍,复制 next 指针,新建链表
- 遍历第二遍,复制 random 指针,查找每一个 random 节点的位置
class Solution {
public:
ListNode *copyRandomList(ListNode *head) {
ListNode* dummy=new ListNode (-1),*tail=dummy;
if(!head) return dummy->next;
//遍历一遍,复制next指针
for(auto p=head;p;p=p->next)
tail=tail->next=new ListNode(p->val);
//遍历第二遍,复制random指针
tail=dummy->next;
for(auto p=head;p;p=p->next,tail=tail->next)
if(p->random)//从头开始寻找random指针指向的地方
{
auto t=dummy->next,t2=head;//t和t2分别指向新旧链表
while(t2!=p->random)//两指针同时往后走,直到找到random
{
t=t->next;
t2=t2->next;
}
tail->random=t;
}
return dummy->next;
}
};
哈希做法
暴力复杂度主要用于查找 random 节点,我们可以哈希存储原链表和新链表节点的对应关系,实现O (1) 查找
/**
* 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) {
ListNode* dummy=new ListNode (-1),*tail=dummy;
if(!head) return dummy->next;
unordered_map<ListNode*,ListNode*> hashtable;
//遍历一遍,复制next指针,同时记录新旧链表节点的对应关系
for(auto p=head;p;p=p->next)
{
tail=tail->next=new ListNode(p->val);
hashtable[p]=tail;
}
//遍历第二遍,复制random指针
tail=dummy->next;
for(auto p=head;p;p=p->next,tail=tail->next)
if(p->random)
tail->random=hashtable[p->random];
return dummy->next;
}
};
标签:dummy,head,ListNode,复杂,random,next,链表,tail,复刻
From: https://www.cnblogs.com/tangxibomb/p/17285812.html