时间复杂度O(3N)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
/*struct RandomListNode { int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};*/class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead)
{
if(!pHead)return NULL;
RandomListNode *result,*cur,*tmp;
cur=pHead;
while(cur)//每个节点 后面复制一个自己
{
tmp=new RandomListNode(cur->label);
tmp->next=cur->next;
cur->next=tmp;
cur=tmp->next;
}
cur=pHead;
tmp=cur->next;
while(cur)//复制random连接
{
if(cur->random!=NULL)
tmp->random=cur->random->next;
cur=tmp->next;
if(cur!=NULL)//链表尾部的处理
tmp=cur->next;
}
//拆分两个表
cur=pHead;
result=cur->next;
tmp=result;
while(cur)
{
cur->next=tmp->next;
cur=cur->next;
if(cur!=NULL)//链表尾部的处理
{
tmp->next=cur->next;
tmp=tmp->next;
}
}
return result;
}
}; |