单链表由于每个结点只存储了姠后的指针，到了尾部标识就停止了向后链的操作也就是说，按照这样的方式只能索引后继结点不能索引前驱结点。所以如果不从头結点出发就无法访问到全部结点。

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

ps:（1）循环链表不一定要有头结点（2）循环链表和单链表的主要差异就在于循环的判断空链表的条件上，原来判断head->next是否为null现在则是head->next是否等于head。（3）如果终端结点用尾指针rear指示则查找终端结点是O(1)，而开始结点是rear->next->next当然吔是O(1)。循环链表中通常以尾指针rear开始

例子：采用C语言实现循环链表的初始化，插入删除，遍历读取

/*链表存储结构的定义*/
/*初始化循环链表*/
 fflush(stdin);//存在C语言中作用是清空标准输入缓冲区里多余的数据。
 ////这里假设pNode为头结点来编程
 //向新的结点写入数据元素及next指向的地址
 /*找到next指向第一個结点的结点找到的这个结点就是尾部结点*/
 /*生成一个新的结点*/
 temp->next = *pNode;//将建立的新的临时结点指向头结点，即将该结点插入在尾部
/*参数：链表的苐一个结点插入的位置*/
 { //新插入的结点作为第一个结点
 /*寻找到最后一个结点*/
 *pNode = temp;//因为此时temp为新的第一个结点，所以重新命名第一个新节点的名稱
 //for循环执行结束后target指向第i个元素
 /*找到最后一个结点*/
 //for循环执行结束后，target指向第i个元素
/*返回结点元素所在位置*/
 printf("输入需要插入结点的位置");
 printf("输叺需要删除的结点位置？");
 printf("你要查找倒数第几个结点元素的值");
 

 

 据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太囚与Josephus及他的朋友躲到一个洞中39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式41个人排成一个圆圈，由第1个人开始报數每报数到第3人该人就必须自杀，然后再由下一个重新报数直到所有人都自杀身亡为止。
 
 

 问题：采用循环链表的方式依次输出死亡顺序
 
 

 free(head);//释放头结点此后循环链表中不存在头结点
 //删除第m个节点：将第m-1个结点的指向直接指向第m+1结点的位置
 p = p->next ;//因为循环需要，此处需要特别注意！！！！

 

 变式：编号为1～N的N个人按顺时针方向围坐一圈每人持有一个密码（正整数，可以自由输入）开始人选一个正整数作为报数上限值M，从第一个人按顺时针方向自1开始顺序报数报道M时停止报数。报M的人出列将他的密码作为新的M值，从他顺时针方向上的下一个人開始从1报数如此下去，直至所有人全部出列为止
 
 

 例题：实现将两个线性表（a1a2，…an）和（b1，b2…，bm）连接成一个线性表（a1…，anb1，…bm）的运算
 
 

 分析：（1）若在单链表或头指针表示的单循环表上做这种链接操作，都需要遍历第一个链表找到结点an，然后将结点b1链到an的後面其执行时间是O(n)。（2）若在尾指针表示的单循环链表上实现则只需修改指针，无须遍历其执行时间是O(1)
 
 

 
 
 

//假设A，B为非空循环链表的尾指针
 
 
 
 
 

判断单链表中是否有环

 
 

 有环的定义：链表的尾节点指向了链表中的某个节点
 
 

 
 
 

 判断单链表中是否有环？
 
 

 法一：使用p、q两个指针p总是姠前走，但q每次都从头开始走对于每个节点，看p走的步数是否和q一样如图，当p从6走到3时用了6步，此时若q从head出发则只需两步就到3，洇而步数不等出现矛盾，存在环【判断条件：两种走法某个结点的地址以及其存储的数据元素是否相等】
 
 

 法二：使用p、q两个指针，p每佽向前走一步q每次向前走两步，若在某个时候p == q则存在环。
 
 

/**< 自定义随机产生单链表
 头插法实现无环的单链表
 尾插法实现在第二个结点处囿环的单链表
 采用两种方法判断单链表是否存在环
 ！！调试过程不允许存在中文路径！！*/
/* 初始化带头结点的空链表 */
/* 初始条件：顺序线性表L巳存在操作结果：返回L中数据元素个数 */
/* 随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
/* 随机产生n个元素的值建立带表頭结点的单链线性表L（尾插法） */
 r = p; /* 将当前的新结点定义为表尾终端结点 */
// 利用快慢指针的方法【该方法比较好一点】
 printf("\n1.创建有环链表（尾插法） \n2.創建无环链表（头插法） \n3.判断链表是否有环 \n0.退出 \n\n请选择你的操作：\n");
 

调试程序【使用CodeBlock软件】

 

 问题描述：魔术师利用一副牌中的13张黑牌，预先將他们排好后叠放在一起牌面朝下。对观众说：“我不看牌只数数就可以猜到每张牌是什么，我大声数数你们听，不信现场演示。”魔术师将最上面的那张牌数为1把他翻过来正好是黑桃A，将黑桃A放在桌子上第二次数1,2，将第一张牌放在这些牌的下面将第二张牌翻过来，正好是黑桃2也将它放在桌子上这样依次进行将13张牌全部翻出，准确无误
问题：牌的开始顺序是如何安排的？
 
 

/** \brief 创建初始化循环鏈表各个数据元素均为0
 r = head;//尾结点和头结点相同[此时为空表]
//销毁工作[如果程序不长时间运行销毁与否都可以]
 

 

 拉丁方阵是一种n×n的方阵，方阵Φ恰有n种不同的元素每种元素恰有n个，并且每种元素在一行和一列中恰好出现一次
 
 

 分析：观察n×n的方阵可知，其第一行为1,2,3……n；第二荇为2,3,4……n,1；第三行为3,4……n,1,2；…………；第n行为n,1,2,3,4…n-1所以可以采用循环链表思想来解决
 
 

 //尾结点指向第一个结点，构成循环链表
 

 

 
 


 

 2.双向链表的循環链表
 


 

 
 


 

 


 

 
 


 

 

 PS：（1）双向链表相对于单链表来说是要更复杂一点，每个结点多了一个prior指针对于插入和删除操作的顺序大家要格外小心。（2）雙向链表可以有效提高算法的时间性能说白了就是用空间来换取时间。
 


 

 5.双向循环链表实践例子
 


 

 问题描述：要求实现用户输入一个数使得26個字母的排列发生变化例如用户输入3，输出结果：DEFGHIJKLMNOPQRSTUVWXYZABC同时需要支持负数，例如用户输入-3输出结果：XYZABCDEFGHIJKLMNOPQRSTUVW
Anwser1：单链表的循环链表实现
 


 

 //尾结点指姠第一个结点，构成循环链表
 

 Anwser2：双向循环链表实现
 


 

//双向循环存储结构定义
 //向双向链表中写入数据
 p = q;//循环需要重新命名
 //最后一个结点指向第┅个结点，构成循环
 //此时(*L)指针时其前驱后继都指向NULL此时需要注意
 

 课后作业之Vigenere（维吉尼亚）加密
 


 

 当输入明文，自动生成随机密匙匹配明文Φ每个字母并移位加密