java - 关于使用数组表示约瑟夫斯谜题

Question

Robert Sedwick 的算法，提到链表可以用数组表示，链接如下

http://flylib.com/books/en/3.55.1.34/1/

图 3.8，这里如果从我的理解中删除了 5，接下来 4 应该更改为索引 6，因为删除了 val 5，因为我们遍历了第 4 项的数字，接下来更改了 val 3。我没有遵循图中的逻辑。任何人都可以帮助我吗？

谢谢!

Answer 1

索引是从零开始的，而不是值本身(字母会是更好的值)。
移除值5示例:移除前，值为4的节点的下一个索引为4，指向值5；删除后，下一个索引更改为 5，指向值 6(下一个从 4 更改为 5)。

或者，使用前缀 v 来表示值:

之前

    index ...  3  4  5 ...
    ----------------------
    value     v4 v5 v6
    next       4  5  6

之后

    index ...  3  4  5 ...
    ----------------------
    value     v4 v5 v6
    next       5  5  6  

如您所见，节点 v4 后跟 v6(索引 5)实际上从链中删除了 v5。