我最近偶然发现一个论坛，声称Josephus问题可以用数据结构在O（n）中解决。这里的明确选择是一个循环链表，但我声称它只能在O（kn）或O（n^2）中完成，除非你在维基百科上做数学递归/迭代josephus算法。首先，循环链表具有以下属性：搜索O（n）、删除O（1）、追加O（1。这假设delete是一个给定的节点，append替换了头或尾。
如果我们有一个循环的节点列表，我们可以从起点找到要删除的节点，如下所示：
n=6个节点
k=删除每3个节点
起点：节点#0
节点：0、1、2、3、4、5
我们可以通过（k+StartingPoint-1）%n.计算要删除的节点。对于startpoint=0，我们有（3+0-1）%6=2。现在，3将是我们的起点。（3+3-1）%5=0，当移位时，它是我们原来的5节点（即，由于原来的2不存在，数字现在将为0,1,2,3,4）。这基本上就是数学版本的工作原理。对于链表，我们可以类似地导出哪个节点需要删除。问题是我们必须去这个节点。链表具有O（n）搜索，这是一个问题。所以我们遍历到这个节点，删除它，现在我们有n=n-1。我们找到下一个索引，进行O（n）搜索，得到n=n_original-2。这变成n+（n-1）+（n-2）+…=O（n^2）。
如果我们有一个双链接的循环列表，那么如果节点离我们更近，我们就不必走完全程。不过，如果k小于n，这是O（k）搜索，如果k大于n，这就是O（n）搜索（因为在到达起点之前，你只能移动n个节点，但如果k很小，你只需要移动k，就不会到达起点）。
无论如何，我的观点是，我看不出如何通过O（n）中的数据结构来实现这一点。维基百科上的解决方案是O（n）中一种非常优雅的数学方法，它显示了递归的力量（纯粹通过调用堆栈来跟踪旧的起点，等等），但当删除实际对象时，似乎不可能得到O（n）。我想展示我在弄清楚这一点上的尝试，而不仅仅是明目张胆地问，那么有人知道用某种数据结构在O（n）中做到这一点的方法吗？谢谢
我在博客上用O（n）时间的循环链表解决了这个问题。该网站还有一个使用队列的O（n）解决方案和一个使用纯（非循环）链表的O（n^2）解决方案。对于循环链表，您总是向前移动，而不是向后移动，正如您对双链表所建议的那样。
举个例子，看看你的清单。您从0开始，计数3，然后删除项目3。然后计数3并删除0。然后计数3并删除4。然后计数3并删除2。然后计数3并删除5。最后数3，删除1。所采取的步骤总数为kn，其中n为节点数，k为步长。但这是节点数量的O（n），因为n是问题大小，k是常数。