1、问题

Josephu(约瑟夫、约瑟夫环) 问题
Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

2、解决方法

使用环形单向链表来解决

  1. package com.study.linkedlist;
  3. public class CircleSingleLinkedList {
  5.     private Player first =  null;
  7.     public void add(int no){
  8.         if(no<1){
  9.             System.out.println("值错误");
  10.             return;
  11.         }
  12.         Player cur = null;
  13.         for (int i = 1; i <= no; i++) {
  14.             Player p = new Player(i);
  15.             if(i==1){
  16.                 first = p;
  17.                 first.next = first;
  18.                 cur = first;
  19.             }else {
  20.                 cur.next = p;
  21.                 p.next = first;
  22.                 cur = p;
  23.             }
  24.         }
  25.     }
  27.     public void show(){
  28.         if(first==null){
  29.             System.out.println("没有指针");
  30.             return;
  31.         }
  32.         Player cur = first;
  33.         while (true){
  34.             System.out.println("指针编号为："+cur.no);
  35.             if(cur.next==first){
  36.                 break;
  37.             }
  38.             cur = cur.next;
  39.         }
  40.     }
  42.     /**
  43.      *
  44.      * @param no 表示从第几个节点开始
  45.      * @param count 表示数几下
  46.      * @param nums 表示一共有多少个节点
  47.      */
  48.     //约瑟夫问题
  49.     public void count(int no,int count,int nums){
  51.         if(first==null || no<1 || no>nums){
  52.             System.out.println("参数有误");
  53.             return;
  54.         }
  56.         Player temp = first;
  57.         while (true){
  58.             if (temp.next==first){
  59.                 break;
  60.             }
  61.             temp = temp.next;
  62.         }
  64.         //先让first和temp移动no-1次
  65.         for (int i = 0; i < no - 1; i++) {
  66.             first = first.next;
  67.             temp = temp.next;
  68.         }
  70.         while (true){
  71.             if(temp==first){
  72.                 System.out.println("最后一个节点为："+first.no);
  73.                 break;
  74.             }
  75.             for (int j=0;j<count-1;j++){
  76.                 first = first.next;
  77.                 temp = temp.next;
  78.             }
  79.             System.out.println("出圈的节点为："+first.no);
  80.                 first = first.next;
  81.                 temp.next = first;
  82.         }
  83.     }
  85. }
package com.study.linkedlist;

public class CircleSingleLinkedListDemo {

    public static void main(String[] args) {
        CircleSingleLinkedList csll = new CircleSingleLinkedList();
        csll.add(5);
        csll.show();
        csll.count(1,2,5);
    }
}

3、测试结果

图片.png