利用循环链表解决约瑟夫问题

问题简介

约瑟夫问题（Josephus Problem）意思是有n个人围成一圈（这个圈可以叫做约瑟夫环），从某一个指定的人开始报数，每报数到一个给定的数，那么将那个人剔除出这个圈，从下一个人开始重新报数，循环往复直到只剩下一个人为止。这个其实很像小时候一群人围坐在一起玩的丢手绢游戏。

关于循环链表

在所有的数据结构里，与约瑟夫环在逻辑结构上最为相似的就是循环链表。在计算器中我们已经实现过使用链式结构的栈，而普通的链表与栈的区别就在于栈只能从顶部加入元素或删除元素，但是链表可以从链式结构中的任意一个位置进行增加，删除，改动的操作，不受先进后出的限制。我们已经知道链式结构通过结点或指针的形式串在一起，在这里不再做介绍。

而循环链表则是一种特殊的链表，在循环链表中，最后一个元素指向第一个元素，首尾相连形成一个链环结构（想到了耶梦加得），这便是循环链表。根据实际需要，我们还分有循环单链表和循环双链表，在这个问题里我们使用循环单链表便足以解决问题。

循环单链表的设计

获得给定位置的节点

由于循环链表可以指定插入元素的位置或删除指定位置的元素，所以获得给定位置的节点是我们首先需要解决的问题。这个问题只需要使用一个指针变量指向第一个节点（虽然循环链表首尾相连没有严格的起始位置，但习惯上我们还是将第一个元素作为第一个节点），通过不断的查找指向的下一个节点，就能查找到指定的节点。

Node getPosition(int position) {
    Node temp = head;
    for (int i = 0; i < position; i++) {
        temp = temp.next;
    }
    return temp;
}

在指定位置插入节点

我们已经有了获得给定位置节点的能力，要在指定位置插入节点只需要获取当前指定位置和指定位置之前的两个节点，先将即将要插入的节点指向当前位置的节点，再将指定位置之前的节点指向要插入的节点，就完成了操作。需要注意的是这一步的顺序一般来说不可更改，如果反过来先将前一个节点指向要插入的节点，那么所有后面的节点都有丢失的风险。另外一个需要注意的地方便是在插入第一个节点的时候需要将第一个节点指向自身，这便自动形成了循环，不需要再在之后进行操作。

void insert(T entry,int position) {
    if (position > count + 1) {
        System.out.println("Overflow");
    }
    else if (isEmpty()){
        Node temp = new Node(entry);
        head.next = temp;
        temp.next = head.next;
        count++;
    }
    else {
        Node temp = new Node(entry);
        temp.next = getPosition(position);
        getPosition(position - 1).next = temp;
        count++;
    }
}

删除指定位置的节点

直接将指定位置的前一个位置的节点指向指定位置所指向的节点就算完成了删除。

void remove(int position) {
    Node temp = getPosition(position - 1);
    temp.next = temp.next.next;
    count--;
}

至此完成了循环单链表最重要的几个方法的设计，下面继续分析约瑟夫问题。

解决约瑟夫问题

约瑟夫问题实际上就是考验循环链表的使用，不断的删除特定位置的节点，不过有一个需要注意的点，虽然我们使用了循环链表，越过了最后一个节点后会自动返回第一个节点，这也就意味着我们可以不用处理待删除节点的位置，任其无限制的增加即可。

打个比方就像是将时钟越过12点称作13点。但我们不会将24点的下一个小时称为25小时一样，如果不处理位置角标，那么任意一个没有意义的整数都可以作为我们删除节点的位置参数，这显然是不合理的，所以我们需要对位置角标进行操作，判断其是否越过最后一个节点，若已经越过则重置为从0计数起的对应位置。所以完整的解决约瑟夫问题的代码如下：

private static void solutionOfJosephusProblem(int start, int space, LinkedList list) {
    while(!list.isEmpty()) {
        while (start + space > list.getSize()) {
            start %= list.getSize();
        }
        list.remove(start + space);
        for (int i = 1; i <= list.getSize();i++) {
            System.out.print(list.retrieve(i) + " ");
        }
        System.out.println();
        start += space - 1;
    }
}