## 问题描述 > 有两个循环单链表，链表头指针分别为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"); } ~~~