循环链表

介绍

很多时候我们找查询链表内的结点，只能方位当前结点以及其后续的结点，无法访问前面的结点。简单举个例子，就比如使用Windows自带文本文档（记事本）的查找功能时，当你没有勾选循环时，你已经查询了某一关键字之后，要查询另一个关键字在其之前（或者之后），在不知道的情况下选反了（如另一个关键字在现关键字之前，选择了向下查询），就会找不到关键字。这种情况下，我们只要将最后一个结点的next域指针指向链表的第一个结点，就形成了一个环，于是，就出现了单循环链表。这样，无论从哪个结点开始，都可以访问整个链表的所有结点。

两循环链表首尾相连

方法一（没有尾指针的）

假设两个链表为L1、L2，结点p1、p2分别指向两个头结点。两个循环链表需要相连，其实就是表L1的最后一个结点的next指针指向p2的next域，然后表L2的最后一个结点的next指针指向p1的next域，释放掉p2。因为没有定义尾结点，所以需要将每个表都遍历一遍直到尾结点。因为要遍历整个链表，所以其时间复杂度为（假设表L1长度为m，表L2长度为n）：O(m+n)。

方法二（带尾指针的）

如果是要将带有尾指针的两个链表进行首尾相连，只需要对指针进行相应的变化即可，无需再进行整个表的遍历，变化如下：

p2=tail2->next;
tail2->next=tail1->next;		//将表L2的尾结点的next域指向表L1的头结点
tail1->next=p2-next;		//将表L1的尾结点的next域指向表L2的首结点（不是头结点！）
free(p2)		//释放表L2的头结点

因为只需要变化指针，所以得出的时间复杂度为：O(1)。

原文地址：http://www.cnblogs.com/qinyu33/p/16919083.html