public class Node {
    public int data;
    public Node next;
 
    public Node(int data) {
        this.data = data;
    }
 
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}

//創(chuàng)建一個first結(jié)點，當前沒有編號
public Node first = new Node(-1);

   
     public void add(int n){
        //其實循環(huán)鏈表，一個結(jié)點也可以循環(huán)，但這里為了方便后面介紹約瑟夫問題
        //我們循環(huán)的結(jié)點不能少于兩個所以做了這個判斷。
        if (n < 2){
            System.out.println("n的值不正確");
            return;
        }
 
        //輔助結(jié)點
        Node end = null;
 
        //使用for循環(huán)來創(chuàng)建鏈表
        for (int i = 1; i <= n; i++) {
 
            //根據(jù)編號創(chuàng)建結(jié)點
            Node node = new Node(i);
 
            //如果是第一個結(jié)點，first頭指向第一個結(jié)點，end表示尾，回過頭來指向first，形成循環(huán)
            if(i == 1){
                first = node;
                end = first;
            }else{
                //先將尾部end的next指向新的結(jié)點node，然后end后移指向新的結(jié)點，
                //再將end的next指向第一個結(jié)點first，這樣就形成了循環(huán)
                end.next = node;
                end = end.next;
                end.next = first;
            }
 
        }
    }

  public void show(Node first){
 
        //判斷循環(huán)鏈表是否為空
        if (first.next == first){
            System.out.println("列表為空！");
            return;
        }
        
        //輔助結(jié)點
        Node temp = first;
        //循環(huán)打印
        while (true){
 
            System.out.println(temp);
            //最后一個結(jié)點的next等于first，就退出
 
            if (temp.next == first){
                break;
            }
 
            temp = temp.next;
        }
    }

public void goOutCircle(int start,int m, int n){
}

        if (n >= 2 && start <= n){
            add(n);
        }else {
            System.out.println("輸入異常！");
            return;
        }

        Node temp = first;
        while (true){
            if (temp.data == start){
                first = temp;
                break;
            }
            temp = temp.next;
        }

        Node end = first;
 
        while (true) {
            //當總數(shù)只有一個的時候，循環(huán)結(jié)束。
            if (n == 1) {
                System.out.println("勝利者為" + first + "號");
                break;
            }
 
            //用for循環(huán)，循環(huán)次數(shù)為 m - 1，因為本身要數(shù)一個數(shù)
            for (int i = 1; i <= m - 1; i++) {
                //first指向下一個結(jié)點
                first = first.next;
                //如果找到了要出圈的結(jié)點，first是正好指向它的
                if (i == m - 1) {
                    //first指向的這個結(jié)點出圈
                    System.out.println(first + "號出圈");
                    //每出圈一個，總數(shù)減一
                    n--;
                    //first繼續(xù)指向下一個結(jié)點
                    first = first.next;
                    //此時end還在出圈結(jié)點的前一個位置，end的next指向first
                    end.next = first;
                    //end也同樣指向first指向的結(jié)點
                    end = first;
                    break;
                }
                //如果沒有到要出圈的結(jié)點，end繼續(xù)跟著first指向同一個結(jié)點
                end = first;
            }
        }

    public void goOutCircle(int start,int m, int n){
        //首先確定圈的大小
        if (n >= 2 && start <= n){
            add(n);
        }else {
            System.out.println("輸入異常！");
            return;
        }
 
        //確定數(shù)數(shù)的位置
        Node temp = first;
        while (true){
            if (temp.data == start){
                first = temp;
                break;
            }
            temp = temp.next;
        }
 
        //進行遍歷
        Node end = first;
        while (true) {
            if (n == 1) {
                System.out.println("勝利者為" + first + "號");
                break;
            }
 
            for (int i = 1; i <= m - 1; i++) {
                first = first.next;
                if (i == m - 1) {
                    System.out.println(first + "號出圈");
                    n--;
                    first = first.next;
                    end.next = first;
                    end = first;
                    break;
                }
                end = first;
            }
        }
    }