题目

解决代码及点评

/*	复杂链表的拷贝，现在有一个复杂链表，完成一个clone函数拷贝一个链表	复杂链表是指	struct Node	{		struct Node* _next;		struct Node* _sibling;  // sibling指向链表中任意一个节点，或者为NULL		int _data;	};	这道题困难之处在于复制sibling节点，因为按照普通思维，复制好普通链表之后	恢复sibling节点指向非常困难	解决办法：	就地复制，再拆分	比如 原始链表是 a->b->c->d   先就地复制 a->a1->b->b1->c->c1->d->d1	就地复制后，sibling指针也很好确定，就是原来那个节点的next，放置好sibling之后，再进行拆分即可*/#include 
    
     #include 
     
      #include "iostream"using namespace std;typedef struct link{	char id;	struct link *pnext;	struct link *pSibling;	} *plink,link;// 创建链表plink creat(){	plink la,lb,lc,ld,le;	la = (plink)malloc(sizeof(link));	lb = (plink)malloc(sizeof(link));	lc = (plink)malloc(sizeof(link));	ld = (plink)malloc(sizeof(link));	le = (plink)malloc(sizeof(link));	la->pnext=lb;	la->pSibling=lc;	la->id='a';	lb->pnext=lc;	lb->pSibling=ld;	lb->id='b';	lc->pnext=ld;	lc->pSibling=NULL;	lc->id='c';	ld->pnext=le;	ld->pSibling=la;	ld->id='d';	le->pnext=NULL;	le->pSibling=NULL;	le->id='e';	return la;		}plink copy(plink l){		plink head2=l;	// 就地复制	while(head2!=NULL)	{		plink temp;		temp = (plink)malloc(sizeof(link));		temp->id=head2->id;					temp->pnext=head2->pnext;		head2->pnext=temp;		head2=temp->pnext;	}	head2=l;	plink headt=l->pnext;	// 设置sibling	while(head2->pnext->pnext!=NULL)	{		if (head2->pSibling!=NULL)		{			headt->pSibling=head2->pSibling->pnext;		}		headt=headt->pnext->pnext;		head2=head2->pnext->pnext;	}	// 拆分链表	headt=l->pnext;	plink l2=headt;	cout<
      
       id<<"->";    while(headt->pnext->pnext->pnext!=NULL)	{		headt->pnext=headt->pnext->pnext;		headt=headt->pnext;		cout<
       
        id<<"->";	} 	cout<
        
         pnext->id<<"->";	return l2;	}// 主函数int main(){	plink l;	l = creat();	plink l2;	l2=copy(l);		system("pause");	return 0;}