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)建一個(gè)first結(jié)點(diǎn)，當(dāng)前沒有編號(hào)
public Node first = new Node(-1);

   
     public void add(int n){
        //其實(shí)循環(huán)鏈表，一個(gè)結(jié)點(diǎn)也可以循環(huán)，但這里為了方便后面介紹約瑟夫問題
        //我們循環(huán)的結(jié)點(diǎn)不能少于兩個(gè)所以做了這個(gè)判斷。
        if (n < 2){
            System.out.println("n的值不正確");
            return;
        }
 
        //輔助結(jié)點(diǎn)
        Node end = null;
 
        //使用for循環(huán)來創(chuàng)建鏈表
        for (int i = 1; i <= n; i++) {
 
            //根據(jù)編號(hào)創(chuàng)建結(jié)點(diǎn)
            Node node = new Node(i);
 
            //如果是第一個(gè)結(jié)點(diǎn)，first頭指向第一個(gè)結(jié)點(diǎn)，end表示尾，回過頭來指向first，形成循環(huán)
            if(i == 1){
                first = node;
                end = first;
            }else{
                //先將尾部end的next指向新的結(jié)點(diǎn)node，然后end后移指向新的結(jié)點(diǎn)，
                //再將end的next指向第一個(gè)結(jié)點(diǎn)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é)點(diǎn)
        Node temp = first;
        //循環(huán)打印
        while (true){
 
            System.out.println(temp);
            //最后一個(gè)結(jié)點(diǎn)的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) {
            //當(dāng)總數(shù)只有一個(gè)的時(shí)候，循環(huán)結(jié)束。
            if (n == 1) {
                System.out.println("勝利者為" + first + "號(hào)");
                break;
            }
 
            //用for循環(huán)，循環(huán)次數(shù)為 m - 1，因?yàn)楸旧硪獢?shù)一個(gè)數(shù)
            for (int i = 1; i <= m - 1; i++) {
                //first指向下一個(gè)結(jié)點(diǎn)
                first = first.next;
                //如果找到了要出圈的結(jié)點(diǎn)，first是正好指向它的
                if (i == m - 1) {
                    //first指向的這個(gè)結(jié)點(diǎn)出圈
                    System.out.println(first + "號(hào)出圈");
                    //每出圈一個(gè)，總數(shù)減一
                    n--;
                    //first繼續(xù)指向下一個(gè)結(jié)點(diǎn)
                    first = first.next;
                    //此時(shí)end還在出圈結(jié)點(diǎn)的前一個(gè)位置，end的next指向first
                    end.next = first;
                    //end也同樣指向first指向的結(jié)點(diǎn)
                    end = first;
                    break;
                }
                //如果沒有到要出圈的結(jié)點(diǎn)，end繼續(xù)跟著first指向同一個(gè)結(jié)點(diǎn)
                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;
        }
 
        //進(jìn)行遍歷
        Node end = first;
        while (true) {
            if (n == 1) {
                System.out.println("勝利者為" + first + "號(hào)");
                break;
            }
 
            for (int i = 1; i <= m - 1; i++) {
                first = first.next;
                if (i == m - 1) {
                    System.out.println(first + "號(hào)出圈");
                    n--;
                    first = first.next;
                    end.next = first;
                    end = first;
                    break;
                }
                end = first;
            }
        }
    }