约瑟夫问题 Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
思路 用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。
/** * @author zl * @create 2020--09--03--19:28 */ public class Josephu { public static void main(String[] args) { CircleSingleLinkedList linkedList = new CircleSingleLinkedList(); linkedList.addBoy(5); linkedList.showBoy(); linkedList.countBoy(2,2,5); } } //定义环形列表 class CircleSingleLinkedList { //创建一个first节点，用于存储第一个节点 private BoyNode first = null; public void addBoy(int nums) { if (nums < 1) { System.out.println("输入的值不正确"); return; } //这个是真正的列表 BoyNode curNode = null;//用于构建环形列表 for (int i = 1; i <= nums; i++) { BoyNode boyNode = new BoyNode(i); if (i == 1) { first = boyNode; first.next = first; curNode = first; } else { curNode.next = boyNode; boyNode.next = first; curNode = boyNode; } } } //查看链表 public void showBoy() { if (first == null) { System.out.println("链表为空"); } BoyNode temp = first; while (true) { if (temp.next == first) { break; } System.out.printf("小孩编号为%d\t", temp.no); temp = temp.next; } System.out.printf("小孩编号为%d\t",temp.no); System.out.println(); } /** * @param startNo 从第几个孩子开始数 * @param countNum 每次数几个数 * @param nums 表示最初有几个孩子在圈中 */ public void countBoy(int startNo, int countNum, int nums) { if (first == null || startNo < 1 || startNo > nums) { System.out.println("输入数据有误"); return; } BoyNode temp = first; //让temp指向最后一个节点，为了结束循环 while (true) { if (temp.next == first) { break; } temp = temp.next; } //报数前，让first和temp同时移动k-1次，移动到指定的第几个孩子开始的数 for (int i = 0; i < startNo - 1; i++) { first = first.next; temp = temp.next; } while (true) { //结束循环条件 if (temp == first) { break; } for (int j = 0; j < countNum - 1; j++) { first = first.next; temp = temp.next; } //找到出圈的节点 System.out.println("出圈"+first.no); //让出圈的节点 = 下一个节点 first = first.next; //将出圈的前一个节点指向出圈的下个节点 temp.next = first; } System.out.println("最后出圈"+first.no); } } //定义节点 class BoyNode { public int no; public BoyNode next; public BoyNode(int no) { this.no = no; } }