约瑟夫环Java实现

/** * 约瑟夫问题 * 设编号为 1，2，… n 的 n 个人围坐一圈， * 约定编号为 k（1<=k<=n）的人从 1 开始报数， * 数到 m 的那个人出列， * 它的下一位又从 1 开始报数，数到 m 的那个人又出列， * 依次类推，直到所有人出列为止， * 由此 产生一个出队编号的序列。 */public class JosephuDemo {    public static void main(String[] args) {        CircleSingleLinkedList circle = new CircleSingleLinkedList();        int n = 5;        circle.build(n);        circle.show();        int[] order = circle.orderOutOfCircle(3, 2, n);        System.out.println(Arrays.toString(order));    }}class CircleSingleLinkedList {    private Node first;    // 构建约瑟夫环    public void build(int n) {        if (n < 1) {            System.out.println("输入的值不正确！");            return;        }        Node cur = null; // 辅助指针，用来帮助构建环形链表        for (int i = 1; i <= n; i++) {            Node node = new Node(i);            if (i == 1) {                first = node;                first.next = first;                cur = first;            } else {                cur.next = node;                node.next = first;                cur = node;            }        }    }    /**     * 返回约瑟夫环问题的出环顺序     * @param start 从第几个开始数     * @param count  数几下     * @param n 最初环中有多少个     * @return     */    public int[] orderOutOfCircle(int start, int count, int n) {        if (first == null || start > n) throw new InvalidParameterException("参数有误");        int[] res = new int[n];        int index = 0;        Node helper = first;        // 让helper指向环形链表的最后那个node        // helper 指向了最后的node，则终止循环        while (helper.next != first) {            helper = helper.next;        }        // 小孩报数前，先让first和helper移动start-1次        for (int i = 0; i < start - 1; i++) {            first = first.next;            helper = helper.next;        }        // 小孩报数时，让first和helper指针同时移动count - 1次，然后出圈        // 这时说明环中只剩下一个node        while (first != helper) {            // 让first和helper同时移动count - 1次            for (int i = 0; i < count - 1; i++) {                first = first.next;                helper = helper.next;            }            // 这时first指向的小孩就是要出圈的小孩            res[index++] = first.value;            first = first.next;            helper.next = first;        }        res[index] = first.value; // 最后留在圈中的小孩也要加入进结果        return res;    }    // 遍历当前环形链表    public void show() {        if (first == null) {            System.out.println("链表为空");            return;        }        Node cur = first;        while (true) {            System.out.print(cur.value + " ");            if (cur.next == first) break;            cur  = cur.next;        }    }}

参考: 韩顺平老师的数据结构