第八章：第8节 PHP数据结构与算法——环形链表强化学习二（约瑟夫问题）
更新于：2017-06-26 20:20:34
真正来玩游戏
（1）先问题简化，从第一个小孩开始数，数2，看看出列的顺序
现在我们已经有了环形链表，并且$first指向了1号小朋友节点，开始数，first就向下移动，2号小朋友节点出不了列，为什么呢？当$first指向2号小朋友节点，然后让2号小朋友出列，是做不到的，如果是让2号小朋友出列，是形成如下图所示的环形列表，
让1号小朋友的next指向3号小朋友，2号就出列了。但是这个$first是指向了2号本身。所以单链表的麻烦事情：★★它不能自己把自己删除掉。
因此必须保证$first前面还有一个指针，如下图所示，在$first的前面添加一个$tail指针
这个时候就可以把2号人物给删除了，先让$first往后走一步，让$first指向3号小朋友，此时tail指向1号小朋友，让tail的next指向$first，就是1号小朋友指向了3号小朋友，2号小朋友就出列了，如下图所示
就是现在需要一个辅助指针，就是在运行之前，要先拿一个指针指向$first的前面，如下图所示
定义一个出圈的函数：
（2）现在把数2做成变量m
改造下出圈的函数：
这次添加8个小朋友，数3下
结果：
（3）再考虑从第几个人数的问题，变量k；和出列显示
再次改造出圈函数：
我们测试的小朋友数不算多，不依靠环形链表也能数过来。假如一旦人多了，比如4000个人，从第31个人，数20，这时候就发现程序的力量了，你人工去数，可想而知。
用程序来完成你能完成的事情，都是快速的完成。