《大话数据结构》--学习笔记11 ***重点***

3.13 循环链表

对于单链表，由于每个结点只存储了向后的指针，到了为标志就停止了向后链的操作，这样，当中某一结点就无法找到它的前驱结点了，就好像我们刚才说的，不能回到从前。

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

循环链表的优点：解决了从当中一个结点出发，访问到链表的全部结点；

为了使空链表与非空链表处理一致，我们通常设一个头结点，当然，这并不是说，循环链表一定要头结点，这需要注意。循环链表带有头结点的空链表如图：

对于非空的循环链表就如图：

其实循环链表和单链表的主要差异：循环的判断条件上

非循环的判断： p->next是否为空。

循环的判断条件： p->next 不等于头结点，则循环末结束。

在单链表中，我们有了头结点时，我们可用O(1)的时间访问第一个结点，但对于要访问最后一个结点，却需要O(n)时间，因为我们需要将单链表全部扫描一遍。

有没有可能用O(1)的时间由链表指针访问到最后一个结点呢？当然可以，不过我们需要改造一下这个循环链表，不用头指针，而是用指向终端结点的尾指针来表示循环链表，此时查找开始结点和终端结点都很方便了。如图：

从上图可以看到，终端结点用尾指针rear指示，则查找终端结点是O(1),而开始结点，其实就是rear->next->rear ,其时间复杂度也为O(1)

举个程序的例子，要将两个循环链表合并成一个表时，有了尾指针就非常简单，比如下面的这两个循环链表，它们的尾指针分别是rearA 和rear B，如图：

要想把它们合并，只需如下操作即可：如图：

p = rearA ->next;                      /*保存A表的头结点，即（1）*/
rearA->next=rearB->next->next;/*将本是指向B表的第一结点（不是头结点）赋值给rearA->next,即（2）*/   
rear B->next = p;  /*将原A的头结点赋值给rearB->next ，即（3）*/
free (p);