所谓的单向循环链表就是让单向链表的首尾相连，组成一个环状。与带环的链表不同之处在于：单向循环链表环的闭合点必须是头节点，如下图所示。

　　构造一个单向循环链表需要遵循以下两点：

　　(1)循环链表在插入第一个元素时，需要程序将第一个元素的指针域指向其自身，也就构成了循环链表。

　　(2)循环链表由单向链表变化而来，循环链表的插入、删除与普通单向链表的不同之处，在于头和尾节点的操作，因为需要将末尾数据元素的指针域指向头节点。单向循环链表的主要操作方法有：追加、遍历、随机插入、随机删除。由于随机插入和随机删除接近单向链表，所以后面只实现追加和遍历部分。

　　例题１：单向循环链表的追加和遍历。

　　单向循环链表的追加与非循环链表的差别在于：追加在尾部的节点必须指向链表头节点。遍历时不能以后继为空做判断，可以用长度或后继为头节点判断是否循环到链表尾。追加新节点的算法步骤如下：

　　(1)临时指针从头节点循环到尾节点。

　　(2)新节点next指针指向头节点。

　　(3)尾节点next指针指向新节点。

　　单向循环链表追加新节点算法的图解如下图所示。

　　程序代码：

　　运行结果：

　　练习１：编程把一个不知长度的普通单向链表转化为循环单向链表。

　　练习２：假如一个循环单向链表不知到长度，编程把它的长度算出来。

　　练习３：循环单向链表的随机插入和随机删除虽然接近单向链表，但从代码的角度来看，是不一样的，请在上例的类中增加随机插入和随机删除功能，然后在中间和头尾插入元素，然后删除它们。

　　例题２：约瑟夫环。

　　传说在犹太战争中，犹太历史学家弗拉维奥·约瑟夫斯和他的40个同胞被罗马士兵包围。犹太士兵决定宁可自杀也不做俘虏，于是商量出了一个自杀方案，他们围成一个圈，从第一个人开始1、2、3重复报数，数到第三个人时将第三个人杀死，然后再数，直到杀光所有人。约瑟夫斯和另外一个人决定不参加这个疯狂的游戏，他们快速地计算出了两个位置，站在那里得以幸存。写一段程序将n个人围成一圈，并且第m个人会被杀掉，计算一圈人中ython算法冬解哪两个人最后会存活。这个问题可以使用循环链出队表解决，如下图所示。

　　解题算法思路如下：

　　(1)在单向循环链表中增加forPoint(循环指出队一针)和prePoint(前一个节点指针)两个指针。

　　(2)每调用一次next方法，循环指针顺着链表向下一个节点移动(prePoint指针同时记录上一个节点)。

　　(3)增加一个删除节点功能。

　　(4)在while循环中，计数器==3时，删除当前指针所指节点，当剩下两个节点时跳出。

　　程序代码：

　　运行结果：

　　上例的编程思路没什么大问题，但不够简单明朗，下面是改编的程序代码：

　　练习４：如果约瑟夫环开始是100个节点，从头节点开始，逢4出队，小于4个退出循环，改编上例，打印出最后的三个节点。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。更多课程请打开“学思营”同步网站：http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社