[数据结构与算法]环形链表约瑟夫环的简单实现（Java）

1.定义节点

package yuesefu;

public class Boy {
    private int no;
    private Boy next;

    public int getNo() {
        return no;
    }

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

    public Boy getNext() {
        return next;
    }

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

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

2.实现约瑟夫环以及基本操作

package yuesefu;

import linklist.GoodsNode;

import java.beans.EventHandler;

public class CircleLinkList {
    // 定义一个辅助节点，始终指向双向链表的第一个节点，并不参与链表的组成
    Boy first = new Boy(-1);

    // 创建双向链表
    public void addCircle(int num) {
        // 临时节点
        Boy temp = null;
        if (num < 1) {
            System.out.println("无效的参数");
            return;
        }
        for (int i = 1; i <= num; i++) {
            Boy boy = new Boy(i);
            if (i == 1) {
                first = boy;
                first.setNext(first);
                temp = first;
            } else {
                temp.setNext(boy);
                boy.setNext(first);
                temp = boy;
            }

        }

    }

    /**
     * 遍历节点
     */
    public void showCircle() {
        if (first == null) {
            System.out.println("双向链表为空");
            return;
        }
        Boy boy = first;
        while (true) {
            if (boy.getNext() == first) {
                break;
            }
            System.out.println("小孩子的编号为：" + boy.getNo());
            boy = boy.getNext();
        }
    }

    /**
     * 实现约瑟夫环
     *
     * @param startNum 从第几个孩子开始
     * @param outNum   数到几的孩子出列
     * @param num      一共有几个孩子
     */
    public void countCircle(int startNum, int outNum, int num) {
        if (startNum < 1 || first == null || startNum > num) {
            System.out.println("参数错误");
            return;
        }
        // 定义辅助节点指向环形链表最后一个元素
        Boy helper = first;
        while (true) {
            if (helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }

        // 让first指向第一个报数的孩子


        for (int i = 0; i < startNum - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();

        }

        // 出列
        while (true) {
            if (first == helper) {
                break;
            }
            for (int i = 0; i < outNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();

            }
            System.out.println("出列的孩子是：" + first.getNo());
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.println("最后一个出列的孩子是" + first.getNo());
    }


}

3.简单测试

package yuesefu;

public class CircleLinkListTest {
    public static void main(String[] args) {
        CircleLinkList circleLinkList = new CircleLinkList();
        circleLinkList.addCircle(6);
        circleLinkList.showCircle();
        circleLinkList.countCircle(3, 3,6);
    }
}