0%

循环链表

将单链表中终端节点的指针由空指针改为指向头节点,就使整个单链表形成一个环, 这种头尾相接的单链表称为单循环链表,简称循环链表(circular linked list)

循环链表解决了一个很麻烦的问题。如何从当中一个节点出发,访问到链表的全部节点。

为了使空链表与非空链表处理一致,我们通常设一个头节点,当然,这并不是说, 循环链表一定要头节点,这需要注意。

空循环链表: 3-13-3.png

非空循环链表: 3-13-4.png

其实循环链表和单链表的主要差异就在于循环的判断条件上,原来是判断 p->next 是否为空, 现在则是 p->next 不等于头节点,则循环未结束。

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

有没有用 O(1) 的时间由链表指针访问到最后一个节点呢?当然可以。

不过我们需要改造一下这个循环链表,不用头指针,而是用指向终端节点的尾指针来表示循环链表, 此时查找开始节点和终端节点都很方便了。

3-13-5.png

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

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

3-13-6.png

要想将它们合并,只需要如下的操作即可:

3-13-7.png
1
2
3
4
p = rearA->next; // 保存 A 链表的头节点
rearA->next = rearB->next->next; // 将本是指向 B 的第一个节点(不是头节点)赋值给 rearA->next
rearB->next = p; // 将原 A 表的头节点赋值给 rearB->next
free(p); // 释放 p