Tim的资源站

对于单链表而言，最后一个结点的指针域是空指针。如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了循环单链表，如下图所示：

带头结点的循环单链表:

在循环单链表上的操作基本上与非循环链表相同，只是将原来判断指针是否为 NULL 变为是否是头指针，没有其他较大的变化。

对于单链表，只能从头结点开始遍历整个链表；而对于循环单链表，则可以从表中任意结点开始遍历整个链表。

不仅如此，有时对链表常做的操作是在表尾、表头之间进行。此时可以改变链表的标识方法，不用头指针而用一个指向尾结点的指针 R 来标识，可以使操作效率得以提高。

例如，对两个循环单链表 H1、H2 的连接操作，是将 H2 的第一个数据结点接到 H1 的尾结点。如用头指针标识，则需要找到第一个链表的尾结点，其时间复杂度为 O（n）；而链表若用尾指针 R1、R2 标识，则时间复杂度为 O(1)。操作如下：

p = R1–>next；　　　　　//保存 R1 的头结点指针

R1->next = R2->next->next；　　//头尾连接

delete R2->next；　　　　//释放第二个表的头结点

R2->next = p；　　　　　//组成循环链表

这一操作过程如下图所示：

两个用尾指针标识的单循环链表的连接: