/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
RandomListNode* Duplicate(RandomListNode* pHead)
{
RandomListNode* p=pHead;
while(p)
{
RandomListNode* temp=(RandomListNode*)malloc(sizeof(RandomListNode));
temp->label=p->label;
temp->next=p->next;
p->next=temp;
p=temp->next;
}
return pHead;
} RandomListNode* RandomList(RandomListNode* pHead)
{
RandomListNode* p=pHead;
RandomListNode* pnext=NULL;
while(p)
{
pnext=p->next;
if(p->random)
{
pnext->random=p->random->next;
}
p=pnext->next;
}
return pHead;
}
RandomListNode* split(RandomListNode* pHead)
{
RandomListNode* result=pHead->next;
RandomListNode* p=pHead;
RandomListNode* p1=result;
while(p)
{
p->next=p1->next;
p=p->next;
if(p)
{
p1->next=p->next;
p1=p1->next;
}
}
return result;
} RandomListNode* Clone(RandomListNode* pHead)
{
if(!pHead)
return NULL;
RandomListNode* p1=Duplicate(pHead);
RandomListNode* p2=RandomList(p1);
RandomListNode* result=split(p2);
return result;
}
};
要注意各种指针为空的边界条件。在split函数中，必须一趟完成两个链表的拆分，不然就会出现超时错误。