约瑟夫（丢手帕）问题的解决（可复制代码直接运行）

问题介绍，N小孩围成一个圈，从第K个小孩开始报数，数M个数，数到谁，谁出列，问出列的顺序是怎样
问题分析：解决此问题，本次使用环形链表链表实现。由于本列表没有一个空的头链表，所以我们按照第一个加入的小孩算头。

根据单链表的思想，小孩出列即为删除数据，单链表的删除数据是找到此条数据的前驱然后 改变前驱的next地址指向。

所以我们用一个 辅助变量来指向尾部 即 temp.next ==head;

首先我们移动 head到第k个小孩的位置（移动k-1），temp也移动k-1，保证temp在头节点的后面。

然后开始数数，数数也为移动，移动 m-1个位置，temp和head同时移动。

移动到正确的位置后 ，此head位置就是我们要删除的节点,此时temp一直在head的前一个节点（即temp.next =head） .

此处为关键：当head在数完数的位置后，我们要删除这个节点，让head在往后移动一次，temp不动，然后让temp.next = head即可。

QQ截图20191116162701.png

话不多说 上代码

//约瑟夫问题
public class CircleLinkedListDemo {

    public static void main(String[] args) {
        CircleLinkedList cl = new CircleLinkedList();
        cl.add(5);
        cl.yusefu(1, 2, cl.getLength());
    }
}

class CircleLinkedList{
    
     Boy head = null;
     
     //添加小孩
     public void add(int nums){
         if(nums<1){
             System.out.println("最少得一个小孩才能玩");
             return;
         }
         Boy curBoy = null;
         for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            if(i==1){
                head = boy;
                head.next =head;
                curBoy = head;
            }else{
                curBoy.next = boy;
                boy.next = head;
                curBoy = curBoy.next;
            }
         }
     }
     
     //显示有多少个小孩在玩
     public void show(){
         if(head==null){
             System.out.println("没有小孩在玩!");
             return;
         }
         Boy curBoy = head;
         boolean flag = true;
         while(flag){
             if(curBoy.next==head){
                 flag = false;
             }
             System.out.println(curBoy);
             curBoy = curBoy.next;
         }
     }
     
     //解决约瑟夫问题
     public void yusefu(int k,int m,int n){//k从第几个人开始数,m数几下,n有多少人
         Boy temp = head;
         if(head==null||k<0||k>n){
             System.out.println("参数不对,结束游戏!");
             return;
         }
         while(true){
             if(temp.next==head)break;
             temp = temp.next;
         }
         for(int i=0;i<k-1;i++){
             head = head.next;
             temp = temp.next;
         }
         while(true){
             if(temp==head) break;
             for(int i=0;i<m-1;i++){
                 head = head.next;
                 temp = temp.next;
             }
             System.out.println(head.no+"号小孩出圈");
             head = head.next;
             temp.next = head;
         }
         System.out.println("最后出圈得小孩是:"+temp.no);
     }
     
     //获取环形链表得长度
     public int getLength(){
         if(head==null){
             System.out.println("环形链表为空!");
             return 0;
         }
         Boy temp = head;
         int count=0;
         while(true){
            count++;
            if(temp.next==head)break;
            temp = temp.next;
            
         }
         return count;
     }
     
}

class Boy{
    public int no;
    public Boy next;
    
    public Boy(int no){
        this.no=no;
    }

    @Override
    public String toString() {
        return "Boy [no=" + no + "]";
    }
}