//節(jié)點(diǎn)類
class JNode {
    private int id;
    private JNode next;

    public JNode(int id) {
        this.id = id;
    }

    public int getId() {
        return id;
    }

    public JNode getNext() {
        return next;
    }

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

//鏈表類
class CircleSingleLinkedList {
    private JNode first = null; //定義第一個(gè)節(jié)點(diǎn)，未創(chuàng)建時(shí)為null

    //添加節(jié)點(diǎn)，構(gòu)建環(huán)形鏈表
    public void add(int num) {
        if (num < 1){
            System.out.println("創(chuàng)建個(gè)數(shù)不符合規(guī)定！");
            return;
        }
        JNode curNode = null; //輔助變量
        for (int i = 1; i <= num; i++) {
            JNode newNode = new JNode(i);
            if (i == 1){ //第一個(gè)節(jié)點(diǎn)較為特殊
                first = newNode; //真正創(chuàng)建了第一個(gè)節(jié)點(diǎn)
                first.setNext(first); //形成環(huán)狀
                curNode = first; //讓輔助變量開始作用
            }else { //第二個(gè)及其之后節(jié)點(diǎn)
                curNode.setNext(newNode); //讓當(dāng)前節(jié)點(diǎn)指向新建的節(jié)點(diǎn)
                newNode.setNext(first); //讓新建的節(jié)點(diǎn)指向第一個(gè)節(jié)點(diǎn)，形成環(huán)狀
                curNode = newNode; //更新輔助變量
            }
        }
    }

    //遍歷鏈表
    public void list(){
        if (first == null){
            System.out.println("鏈表為空！");
            return;
        }
        JNode temp = first;
        while (true){
            System.out.printf("取出節(jié)點(diǎn)%d\n",temp.getId());
            if (temp.getNext() == first){ //說明已經(jīng)遍歷到最后一個(gè)了
                break;
            }
            temp = temp.getNext();
        }
    }

    //根據(jù)參數(shù)讓節(jié)點(diǎn)出圈（Josepfu）
    public void josepfu(int startNode,int count,int num){ //startNode為開始的那個(gè)節(jié)點(diǎn)，count為每次數(shù)第幾個(gè)，num為鏈表節(jié)點(diǎn)個(gè)數(shù)
        if (first == null || startNode < 1 || count < 1 || startNode > num){
            System.out.println("鏈表為空或者輸入的參數(shù)不符合標(biāo)準(zhǔn)！");
            return;
        }
        //讓first移動(dòng)到startNode指定的節(jié)點(diǎn)，即移動(dòng)startNode-1次
        for (int i = 0; i < startNode - 1; i++) {
            first = first.getNext();
        }
        //創(chuàng)建一個(gè)輔助變量，讓其指向最后一個(gè)節(jié)點(diǎn)（first前一個(gè)）
        JNode helper = first;
        while (helper.getNext() != first){
            helper = helper.getNext();
        }
        //開始按照要求出圈，每次都讓helper和first移動(dòng)count-1次
        while (true){
            if (helper == first){ //圈中只剩下一個(gè)節(jié)點(diǎn)
                break;
            }
            for (int i = 0; i < count - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //此時(shí)first指向的即為要出圈的節(jié)點(diǎn)
            System.out.printf("節(jié)點(diǎn)%d出圈\n",first.getId());
            //將出圈的節(jié)點(diǎn)從鏈表中移除
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("節(jié)點(diǎn)%d為最后一個(gè)節(jié)點(diǎn)",first.getId());
    }
}

/**
 * @Author: Yeman
 * @Date: 2021-10-15-22:33
 * @Description:
 */
public class JosepfuTest {
    public static void main(String[] args) {

        CircleSingleLinkedList linkedList = new CircleSingleLinkedList();

        linkedList.add(5);

        linkedList.list();
        System.out.println("===================");

        linkedList.josepfu(1,2,5);
    }
}