## 問題描述 > 有兩個循環單鏈表，鏈表頭指針分別為h1和h2，編寫一個函數將鏈表h2連接到鏈表h1之后，要求鏈表后的鏈表仍保持循環鏈表的形式 ## 算法思想 > 因為這是兩個循環單鏈表，僅僅只是考慮將它們連接起來形成新的循環單鏈表即可。 那么我們首先找到第一個循環單鏈表h1的尾結點，然后讓其next域指向另一個循環單鏈表h2的第一具有數據域的結點（即頭節點的next域所指的那個結點），此時便可以釋放掉循環單鏈表h2的頭節點；最后在找到循環單鏈表h2的尾結點，使其next域重新指向循環單鏈表h1的頭節點便可。 如此以來便將兩個循環單鏈表連接在一起，形成了一個循環單鏈表。 ## 算法描述 ~~~ //尋找循環單鏈表“最后一個結點” LNode* FindRear(LNode *head) { LNode *p=head->next; while(p->next!=head){ p=p->next; } return p; } //連接兩個循環單鏈表 LinkList Connect(LNode *head1, LNode *head2) { LNode *r1=FindRear(head1); LNode *r2=FindRear(head2); LNode *p=head2->next; r1->next=p; free(head2); r2->next=head1; return head1; } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; LinkList CreatList(LNode*); LinkList Connect(LNode*, LNode*); LNode* FindRear(LNode*); void Print(LNode*); int main(int argc,char* argv[]) { LNode *head1; head1=(LNode*)malloc(sizeof(LNode)); head1=CreatList(head1); LNode *head2; head2=(LNode*)malloc(sizeof(LNode)); head2=CreatList(head2); Print(head1); Print(head2); head1=Connect(head1, head2); Print(head1); return 0; } //尾插法建立循環單鏈表 LinkList CreatList(LNode *head) { LNode *L; LNode *r=head; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; r->next=L; r=L; scanf("%d",&x); } r->next=head; return head; } //連接兩個不同的循環單鏈表 LinkList Connect(LNode *head1, LNode *head2) { LNode *r1=FindRear(head1); LNode *r2=FindRear(head2); LNode *p=head2->next; r1->next=p; free(head2); r2->next=head1; return head1; } //尋找最后一個結點 LNode* FindRear(LNode *head) { LNode *p=head->next; while(p->next!=head){ p=p->next; } return p; } //打印全部結點 void Print(LNode *head) { LNode *p=head->next; while(p!=head){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~