约瑟夫问题-使用单链表进行一圈人报数

问题：人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，处刑下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。

翻译过来就是，编号1…n的n个人围成一个环，约定编号为k的人开始报数，数到m的人出列，他的下一位又开始从1报数…以此类推。输出出队编号。

（设定1<= k <=m）

package com.youdef.DataStructure.linkedlist;
/*
约瑟夫单向环形链表

1. 有n个节点的单循环链表
由第k节点开始计数m，删除对应的
从被删除结点的下一个节点从1开始计数
直到最后一个结点被删除。
 */
public class JosephuCircle {
    public static void main(String[] args) {
        CircleSingleLinkedList csl = new CircleSingleLinkedList();

        csl.addBoy(14); //添加14个小孩
        csl.showBoy();

        //测试小孩出圈
        csl.countBoy(10,7, 14);
    }
}


/*
first
boy
curBoy 辅助指针用于遍历 从指向first开始
 *///创建单向环形链表
class CircleSingleLinkedList {
    //first结点，当前没编号
    private Boy first = null;

    //创建nums个结点
    public void addBoy(int nums){
        if (nums < 1){ //插入的数值校验
            System.out.println("nums数值不正确");
            return;
        }
        //辅助指针，帮助构建环形链表，辅助指针curBody始终指向最后
        Boy curBoy = null;
        for (int i=1; i<=nums; i++){
            Boy boy = new Boy(i);
            if (i==1){ //第一个小孩节点的话
                first = boy;
                first.setNext(first);  //zhe  构成环！！
                curBoy = first; //辅助指针 指向第一个(这里还是初始化阶段)
            }else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy; //
            }
        }
    }

    //遍历环形列表，打印
    public void showBoy(){
        if (first == null){
            System.out.println("没有任何~~.");
            return;
        }
        Boy curBody = first;
        while (true){
            System.out.printf("小孩编号 %d \n",curBody.getNo());
            if (curBody.getNext() == first){
                break; //遍历结束
            }
            curBody = curBody.getNext(); //指针后移
        }
    }

    /**
     * @param startNo 从第几个小孩开始数数 k
     * @param countNum 数几下，也就是介绍里面的m
     * @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; //辅助指针
        //让helper指向最后一个结点(归位，此时helper在后，first在前)
        while (true){
            if (helper.getNext() == first) break;
            helper = helper.getNext();
        }
        //从第k个小孩开始数，即startNo
        for (int i=0; i<startNo-1; i++){
            first = first.getNext();
            helper = helper.getNext();
        }
        //小孩开始报数，m，first和helper同时移动m-1次
        //first负责出 helper紧随其后，维护指针&链表
        while (true){
            if (helper == first){//圈中 只有一个结点了
                break;
            }
            for (int i=0; i<countNum-1; i++){ //指针同时移动 m-1次
                first = first.getNext();
                helper = helper.getNext();
            }
            //此时first指向要出圈的结点
            System.out.printf("小孩%d出圈\t",first.getNo());
            first = first.getNext();
            helper.setNext(first); //这里操作相当于删除一个结点，维护单链表
        }
        System.out.printf("最后一个小孩 %d\n",first.getNo());

    }
}


//创建Boy节点
class Boy {
    private int no; //编号
    private Boy next; //指向下一个节点

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

    public int getNo(){
        return no;
    }
    public void setNo(int no){
        this.no = no;
    }
    public Boy getNext(){
        return this.next;
    }
    public void setNext(Boy next){
        this.next = next;
    }
}

最终打印：

小孩2出圈	小孩9出圈	小孩3出圈	小孩11出圈	小孩6出圈	小孩1出圈	小孩13出圈	小孩12出圈	小孩14出圈	小孩5出圈	小孩10出圈	小孩4出圈	小孩7出圈	最后一个小孩 8