一 约瑟夫问题描述：
设编号1，2，...n的n个人，围坐一圈，约定编号为k(1<=k<=n)的人开始从1报数，数到m的人出列，他的下一位再从1报数，数到m的人又出列，以此类推，直到所有的人都出列，由此产生一个出队列的编号序列。
例如 n=5,有五个人
k = 1 从第一个人开始报数
m = 2 数两下
由此条件得到出队列的顺序：2->4->1->5->3
二 单向环形链表
节点实体类：
class Node{ private int no;//编号 private Node next;//指向下一节点 public Node(int no) { this.no = no; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } }1：创建一个单项环形链表：
创建一个节点，让first指向该节点，并成环形。
private Node first = new Node(-1);//创建一个first节点，没有编号后面每创建一个节点，就把该节点加入到已有的环形链表
//添加节点，构成一个环形链表 public void addNode(int num){ if(num<1){ System.out.println("数据非法"); return; }else{//使用for循环创建环形链表 Node cur = null; for(int i = 1; i <= num; i++){ Node node = new Node(i); //如果是第一个节点 if(i == 1){ first = node; first.setNext(first);//构成环 cur = first;//让cur指向first节点 }else{ cur.setNext(node); node.setNext(first); cur = node; } } } }2.遍历
先让一个辅助指针cur指向first
通过while遍历环形链表直到 cur.next == first
//遍历 public void showNode(){ //判断first是否为空 if(first == null){ System.out.println("链表为空"); }else{ //创建一个辅助指针 Node cur = first; while (true){ System.out.println("出列的节点编号为："+cur.getNo()); if(cur.getNext() == first){ //遍历完毕 break; }else{ cur = cur.getNext();//cur后移 } } } }测试一下
public static void main(String[] args) { //测试构建和遍历 CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(); circleSingleLinkedList.addNode(200);//加入五个节点 circleSingleLinkedList.showNode(); }三 约瑟夫问题实现
思路：
1.创建一个辅助指针 helper，限制想链表的最后一个节点。
2.报数前先让first和helper移动k-1次。
3.报数时，让first和helper同时移动m-1次。
4.此时first指向的节点出列。
①first = first.next
②helper.next = first
原来的first指向的节点没有被引用，会被回收
public void nodeJosephu(int startNo,int countNum, int nums){ if(first == null||startNo < 1 || startNo > nums){ System.out.println("参数有误"); return; } //创建辅助指针 Node helper = first; while (helper.getNext() != first) {//helper没有指向最后一个节点，则进入循环 helper = helper.getNext();//后移至最后 //报数前先移动k-1次 for (int j = 0; j < startNo - 1; j++) { first = first.getNext(); helper = helper.getNext(); } } //开始报数 while(helper != first){//不是只剩一个节点的时候，进入循环 //让first和helper同时移动countNum - 1 for(int j = 0; j < countNum -1; j++){ first = first.getNext(); helper = helper.getNext(); } //此时first所在节点即为即将出列的节点 System.out.println("约瑟夫问题出列编号为："+ first.getNo()); first = first.getNext(); helper.setNext(first); } System.out.println("约瑟夫问题最后出列节点为："+first.getNo()); }测试一下：
public static void main(String[] args) { //测试构建和遍历 CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(); circleSingleLinkedList.addNode(5);//加入五个节点 //约瑟夫问题测试 circleSingleLinkedList.nodeJosephu(1,2,5); } }结果：
