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

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

空表

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

image-20200407204842506

非空循环链表

对于非空的循环链表就如图所示。

image-20200407205040736

循环链表和单链表的区别

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

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

有没有可能用O(1)的时间由链表指针访问到最后一个结点呢？

不用头指针，而是用指向终端结点的尾指针来表示循环链表（如图所示），此时查找开始结点和终端结点都很方便了。

image-20200407205347154

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

合并两个循环链表

我们想要把两个循环链表合并为一个表，该如何做呢？

有了尾指针就非常简单了。比如下面的这两个循环链表，它们的尾指针分别是rearA和rearB。

image-20200407205724381

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

image-20200407205914723

算法实现思路：

1. 声明一个p指向A表的头结点p = rearA->next;
2. 将rearA的后继指向B表的首元结点rearA->next = rearB->next->next;
3. 将rearB的后继指向A表的头结点；

代码实现：

// 存储空间初始分配量
#define MAXSIZE 20
// ElemtType类型根据实际情况而定，这里假设为int
typedef int ElemType;

typedef struct {
    // 数组存储数据的元素，最多为MAXSIZE个
    ElemType data[MAXSIZE];
    // 线性表当前的长度
    int length;
} SqList;


#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
// Status是函数的类型，其值是函数结果状态代码，如OK等
typedef int Status;

// 线性表的循环链表存储结构
typedef struct NodeTag {
    ElemType data;
    struct NodeTag *next;
} Node;

typedef struct NodeTag *LinkList;


/// 随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）
/// @param L 要初始化的链表
/// @param n 链表的长度
LinkList CreateListTail(LinkList *L, int n) {
    LinkList p,r;
    // 初始化头结点
    *L = (LinkList)malloc(sizeof(Node));
    // 头结点赋值大值
    (*L)->data = 1000;
    // 让头结点的后继指向他自己
    (*L)->next = *L;
    // r为指向尾结点的指针
    r = *L;
    for (int i = 0; i < n; i++) {
        // 生成新的结点
        p = (LinkList)malloc(sizeof(Node));
        // 随机生成100以内的数字
        p->data = rand() % 100 + 1;
        // 新节点的后继指向头结点
        p->next = *L;
        // 让尾结点的后继指向p
        r->next = p;
        r = p;
    }
    return r;
}

合并

LinkList A, B;
LinkList rearA, rearB;

rearA = CreateListTail(&A, 3);
rearB = CreateListTail(&B, 3);

// 合并
// 1、声明p,指向A表的头结点
LinkList p;
p = rearA->next;

// 2、将rearA->next = rearB->next->next;将A表尾结点的后继指向B表的首元结点；
rearA->next = rearB->next->next;
// 3、将rearB->next = p;将B表的后继指向A表的头结点
rearB->next = p;

// 便利输出合并后的链表
LinkList tmp = A->next;
while (tmp != A) {
    printf("%d ", tmp->data);
    tmp = tmp->next;
}

总结

• 循环链表：循环链表实在单链表的基础上，将尾结点的指针，重新指向头结点；
• 构成了一个闭环；
• 循环链表遍历的退出条件在于，p->next不等于头结点；
• 单链表遍历的退出条件在于，p->next不为NULL；