单向环形链表应用场景

public class SingleCircleLinkedListDemo {
    public static void main(String[] args) {
        SingleCircleLinkedList singleCircleLinkedList = new SingleCircleLinkedList();
        singleCircleLinkedList.addBoy(555);
        singleCircleLinkedList.showBoy();

        singleCircleLinkedList.countBoy(1,2,15);
    }
}

/**
 * 创建单向环形链表
 */
class SingleCircleLinkedList {
    // 创建first节点，当前无编号
    private Boy first = null;

    /**
     * 根据用户的输入，计算出小孩出圈的顺序
     * @param startNo
     * @param countNum
     * @param nums
     */
    public void countBoy(int startNo,int countNum,int nums){
        if (first == null || startNo<1 || startNo > nums){
            System.out.println("参数无效，请重新输入~");
            return;
        }

        // 创建辅助指针，协助出圈
        Boy helper = first;
        while(true){
            if (helper.getNext() == first){ // helper指向最后节点
                break;
            }
            helper = helper.getNext();
        }

        // 小孩报数前，先让first和next移动k-1次，到达指针位置
        for (int j = 0;j<startNo-1;j++){
            first = first.getNext();
            helper = helper.getNext();
        }

        // 开始报数时，让first和helper同时移动m-1次，然后出圈
        // 循环，直到圈中只有一个节点
        while(true){
            if (helper == first) // 圈中只有一个节点
                break;
            for (int j = 0;j<countNum-1;j++){ // 移动m-1次
                first = first.getNext();
                helper = helper.getNext();
            }
            // 这是first指向的节点，就是出圈节点
            System.out.println("小孩出圈："+first.getNo());

            // 出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.println("最后小孩出圈："+first.getNo());
    }

    /**
     * 构建环形链表
     *
     * @param nums
     */
    public void addBoy(int nums) {
        if (nums < 1) {
            System.out.println("输入的值不合理，请重新输入~");
            return;
        }

        Boy curBoy = null; // 辅助指针，协助构建环形链表
        // 使用for循环构建环形链表
        for (int i = 1; i <= nums; i++) {
            // 根据编号，创建小孩节点
            Boy boy = new Boy(i);
            // 第一个小孩特殊处理
            if (i == 1) {
                first = boy; // 头结点指向第一个小孩
                first.setNext(first); // 回环
                curBoy = first; // 保证头节点不懂
            } else {
                curBoy.setNext(boy); // 添加新节点
                boy.setNext(first); // 回环
                curBoy = boy; // 移动当前节点
            }
        }

    }

    /**
     * 遍历当前环形链表
     */
    public void showBoy() {
        if (first == null) {
            System.out.println("链表为空~");
            return;
        }

        Boy temp = first; // 保证头结点不动
        while (true) {
            System.out.println("小孩的编号为：" + temp.getNo());
            if (temp.getNext() == first) { // 是否回环(遍历结束)
                break; // 退出循环
            }
            temp = temp.getNext(); // 移动指针
        }
    }
}

/**
 * 定义单向环形链表节点
 */
class Boy {
    private int no;
    private Boy next; // 指向下一节点，默认为null

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

    public int getNo() {
        return no;
    }

    public Boy getNext() {
        return next;
    }

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

    public void setNo(int no) {
        this.no = no;
    }
}