Question

已知有两个带头的结点的循环单链表LA、LB,编写一个算法，将两个循环单链表合并为一个循环单链表

其头指针为LA.

Answer 1

已知带有头结点的两个单链表 la 和 lb 都是非递增有序序列。

编写好的算法实现将这两个链表合并为新的带有头结点的链表 lc ，使得 lc 的元素仍然是非递增有序排列的序列，如果遇到 la 与 lb 中元素相同，则只取 la 中的元素，去掉 lb 中的元素。已知 la 的元素个数 为 m ， lb 的元素个数为 n。

循环单链表是单链表的另一种形式，其结构特点链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。和单链表相同，循环链表也有带头结点结构和不带头结点结构两种，带头结点的循环单链表实现插入和删除操作较为方便。

Answer 2

将两个循环单链表合并为一个循环单链表的算法如下
先找到两个链表的尾，并分别由指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾Q，使它的链域指向第一个表的头结点。
LinkList merge_1(LinkList LA,LinkList LB)
/*此算法将两个链表的首尾连接起来*/
{ Node *p, *q; p=LA; q=LB;
while (p->next!=LA) p=p->next; /*找到表LA的表尾*/
while (q->next!=LB) q=q->next; /*找到表LB的表尾*/
q->next=LA;/*修改表LB 的尾指针，使之指向表LA 的头结点*/
p->next=LB->next;/*修改表LA的尾指针，使之指向表LB 中的第一个结点*/
free(LB);
return(LA);
}