//============================================================================ // Name : 100题之复杂链表的复制.cpp // Author : // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #include <iostream> using namespace std; struct ComlexNode { int value; ComlexNode* next; ComlexNode* pSlibing; ComlexNode(int value1):value(value1),next(NULL),pSlibing(NULL){} }; void copyStep1(ComlexNode**head) { if(!(*head)) return; ComlexNode*p=NULL; ComlexNode*q=NULL; ComlexNode*h=*head; while(h) { p=new ComlexNode(h->value); q=h->next; h->next=p; p->next=q; h=h->next->next; } h=*head; while(h) { cout<<h->value<<" "; h=h->next; } cout<<endl; } void copyStep2(ComlexNode**head) { ComlexNode*h=*head; while(h) { ComlexNode*s=h->pSlibing; if(s) h->next->pSlibing=s->next; else h->next->pSlibing=NULL; h=h->next->next; } h=*head; while(h) { cout<<h->value<<" "; if(h->pSlibing) cout<<h->pSlibing->value<<endl; h=h->next; } cout<<endl; } void copyStep3(ComlexNode**head1,ComlexNode**head2) { ComlexNode*h=*head1; while(h) { if(!(*head2)) { (*head2)=(*head1)->next; } if(h->next) h->next=h->next->next; h=h->next; } } ComlexNode* copyComlexNode(ComlexNode**head) { copyStep1(head); copyStep2(head); ComlexNode*head1=NULL; copyStep3(head,&head1); return head1; } int main() { ComlexNode*head=new ComlexNode(1); head->next=new ComlexNode(2); ComlexNode*p=head->next; head->next->next=new ComlexNode(3); ComlexNode*s=head->next->next; head->pSlibing=p; p->pSlibing=s; ComlexNode*head1=copyComlexNode(&head); while(head) { cout<<head->value<<" "; if(head->pSlibing) cout<<head->pSlibing->value; cout<<endl; head=head->next; } cout<<"head1"<<endl; while(head1) { cout<<head1->value<<" "; if(head1->pSlibing) cout<<head1->pSlibing->value; cout<<endl; head1=head1->next; } return 0; }
