循环链表和约瑟夫问题 Circular list and Josephus problem

曲径通幽，隰有苌楚。夹岸百里，婀娜其实。 每周学习一个算法。

今天是星期六大年初九，该上班的上班，该上学的也马上开学了。今年过年感觉怎么样？你是不是又变胖了？上班的是不是觉得钱包空了？上学的是不是觉得最近不太常用电子支付改用现金了？过年不要玩野了，因为 Koan 带着新的算法回来了。另外再强调一遍，单项式求导已经完成并上传至了最大的同性交友网站，链接如下：https://github.com/Koan317/Differentiate。今年还请继续关注。

本次的算法需要用到特殊的数据结构：循环链表。

链表是创建在堆内存当中的链式存储结构，将尾节点指向头节点便形成了循环链表。链表是动态存储结构，长度可变。每个节点提供了两个信息，一个是当前节点的值，另一个是下一节点的地址。节点定义如下：

链表中有若干节点，同时还有两个标志性节点，即头节点和尾节点，这两个节点在遍历和删除等操作中扮演非常重要的角色。链表定义如下：

约瑟夫问题是一个基于循环链表提出来的问题，问题的内容是，一个旅行社为一个旅行团提供了一项服务，抽取其中一人为其提供免费旅行。抽取的方式是，给所有人编号，从 1 号开始每隔若干人就剔除一个人，数到最后一位回到 1 号，直到剩下最后一人。

我们简单分析就可以看出，只需生成一个顺序表作为所有人的编号，每隔若干项就删除一项，最后剩下的节点值就是享受免费旅行的人的编号。核心算法如下：

完整代码已经上传至同性交友网站：https://github.com/Koan317/Josephus