花了不少时间,首先递归不行,然后看评论方法以为会了,自己写结果发现原来的链表也不能改变,下意识地以为会销毁原来的测试现在的
/*
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 pHead;
RandomListNode* cur = pHead;
while(cur){
RandomListNode* tmp = new RandomListNode(cur->label);
tmp->next = cur->next;
cur->next = tmp;
cur=tmp->next;
}
cur=pHead;
while(cur){
if(cur->random)
cur->next->random=cur->random->next;
else cur->next->random=cur->random;
cur=cur->next->next;
}
cur=pHead;
RandomListNode* ans = pHead->next;
while(cur){
RandomListNode* t=cur->next->next;
if(t){
cur->next->next=t->next;
cur->next=t;
}
else{
cur->next->next=NULL;
cur->next=NULL;
}
cur=cur->next;
}
return ans;
}
};