题目描述
分析:
由于链表存在一个随机指针,所以不能按照普通的方法复制,
按照如下方法复制:我们可以把这种方法叫做借腹生子法。。。。。。
1.先对原链表的每个结点ai复制一个结点bi,插入到ai的后面
2.按照ai的随机指针对bi的随机指针赋值
3.将bi从原始链表中拆分出来得到新链表
RandomListNode* Clone(RandomListNode* pHead) { if(pHead==NULL) return NULL; //第一步:复制ai的样本bi,bi插入到ai的后面 RandomListNode *p=pHead; while(p!=NULL) { int x=p->label; RandomListNode *ins=new RandomListNode(x); ins->next=p->next; p->next=ins; p=ins->next; } //第二步:按照bi的随机指针对bi的随机指针赋值 p=pHead; while(p!=NULL) { RandomListNode *temp=p->next; if(p->random) temp->random=p->random->next; p=temp->next; } //第三步:将bi从原始链表中剥离出来组成新链表 RandomListNode *head=pHead->next; p=pHead; while(p->next!=NULL) { RandomListNode *temp=p->next; p->next=temp->next; p=temp; } return head; }