数据结构-小孩出圈问题(约瑟夫环问题)

假设有m个小孩，数到n的小孩出列，直到全部出去为止。

使用环形链表解决约瑟夫环问题。

package com.linkedlist;

public class JosephuLinkeslist {
    public static void main(String[] args) {

        Josephu j=new Josephu();

        j.output(5,2,1);
    }
}
class Josephu{
    private Boy first=null;
    public  void add(int num){
        Boy temp=null;
        for (int i = 1; i <= num; i++) {
            Boy boy =new Boy(i);
            if( i == 1){
                first = boy;
                first.setNext(first);
                temp = boy;
            }else{
                temp.setNext(boy);
                boy.setNext(first);
                temp = boy;
            }
        }
    }
    public void show(){
        if(first == null){
            return;
        }
        Boy temp = first;
        while(true){
            System.out.println(temp.getI());
            temp = temp.getNext();
            if(temp == first){
                break;
            }
        }
    }

    /**
     *
     * @param m 表示多少个小孩
     * @param n 表示数几次出圈
     * @param start 从第几个开始数
     */
    public void output(int m,int n,int start){
        add(m);
        if(first == null || start < 1 || start > m) {
            return;
        }
        Boy temp = first;
        while(true){
            if(temp.getNext() == first){
                break;
            }
            temp = temp.getNext();
        }
        for (int i = 0; i < start -1; i++) {
            first = first.getNext();
            temp = temp.getNext();
        }
        while(true){
            if(temp == first){
                break;
            }
            for (int i = 0; i < n-1; i++) {
                first = first.getNext();
                temp = temp.getNext();
            }
            System.out.println(first .getI());
            first = first.getNext();
            temp.setNext(first);
        }
        System.out.println("最后："+temp.getI());

    }

}
class Boy{
    private int i;
    private Boy next;

    public int getI() {
        return i;
    }

    public void setI(int i) {
        this.i = i;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    public Boy(int i){
        this.i=i;
    }
}