java使用单循环链表解决约瑟夫问题

约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（以编号 1，2，3，…，n 分别表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，要求找到最后出列的那个人。

例如有 5 个人，要求从编号为 1 的人开始，数到 2 的那个人出列：

出列顺序依次为：
编号为 1 的人开始数 1，然后 2 数 2，所以 2 先出列；
2 出列后，从 3 开始数 1，4 数 2，所以 4 出列；
4 出列后，从 5 开始数 1，1 数 2，所以 1 出列；
1 出列后，从 3 开始数 1，5 数 2，所以 5 出列；
最后只剩下 3 。

第一步

使用一个first指针指向最开始的数
使用一个current指针指向末尾的数

第二步

从 1 开始数2后，first指针和current指针同时顺时针向前移动（2-1）次:
first = first.next;
current = current.next;
得到下图:

第三步

此时已经确定出列的数字为 2。
将first指针再向前移动一次:first = first.next;
得到下图：

此时将current指针指向的结点的next域指向当前first指针向的结点：current.next = first;
得到下图：

此时 2 结点就被排除在外了，由于java的垃圾回收机制，没有任何引用指向 2 结点，2结点会被回收。

然后往复2，3步直到剩下最后一个结点

    /**      * 约瑟夫问题      * @param oneCycleSingleLinkedList      * @param num      */     public void joseph(OneCycleSingleLinkedList oneCycleSingleLinkedList, int num) {         //恰好再添加结点时，current就指向最后一个结点，first指向第一个结点，可以直接拿来用         Node2 current = oneCycleSingleLinkedList.current;         Node2 first = oneCycleSingleLinkedList.first;         while(first.next != first){             for (int i = 0; i < num - 1; i++) {                 first = first.next;                 current = current.next;             }             System.out.println(first);             first = first.next;             current.next = first;         }     } }  

跳出循环的条件是：

最后一张图：

first和current指向的是同一个结点，
所以first.next = current.next = first,即first.next = first;
此时跳出循环