博客

约瑟夫问题思路分析：编写方法时需要指定开始报数的节点编号（startNo），报数到几(countNum)做出圈动作，以及链表中现在有几个节点。

第一步：判断输入参数的合理性，如果first节点为null，或者开始报数的节点编号小于1，或者开始报数的节点编号大于链表中节点个数，都说明参数有问题，结束执行。

第二步: 报数前应创建一个辅助指针(helper)指向链表的最后一个元素，并且将指向第一个节点的指针(first)和辅助指针一起向后移动startNo-1次，使first指向开始报数的节点，helper指针指向first指针的前一个节点

第三步： 开始报数并出圈，将first指针和helper指针一起后移countNum-1次，此时的first指针就指向了本次要出圈的节点。出圈类似于删除节点，first指针后移，helper指针的next域指向first指针执行的节点。

代码如下：

public class Josepfu {
    public static void main(String[] args) {
        //测试
        CircleSingleLinkedList list = new CircleSingleLinkedList();
        list.addBoy(5);
        list.list();

        //测试约瑟夫问题
        list.countBoy(1,2,5);
    }
}


class CircleSingleLinkedList {
    //创建一个first节点，当前没有编号
    private Boy first = new Boy(-1);
    //添加节点，构成环形
    public void addBoy(int nums){
        if (nums < 1){
            System.out.println("nums参数不正确！");
            return;
        }
        //循环链表的创建
        Boy curBoy = null; //辅助创建指针
        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); //当前节点的next域指向新添加的节点
                boy.setNext(first); //新添加的节点next指向第一个节点
                curBoy = boy;   //当前指针后移，指向最后添加进来的节点
            }
        }
    }

    //遍历环形链表
    public void list(){
        //判断是否为空
        if(first == null){
            System.out.println("链表为空");
            return;
        }
        Boy curBoy = first;
        while(true){
            System.out.println("当前输出的节点编号为:"+curBoy.getNo());
            if (curBoy.getNext() == first){  //已经到达最后节点
                break;
            }
            curBoy = curBoy.getNext();  //没遍历完，指针后移
        }
    }

    /**
     * 根据输入的数据，让节点从环形链表中按规则出圈
     * @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){
                break;
            }
            helper = helper.getNext();
        }
        //开始报数前，应将first和helper指针向后移动startNo-1次
        for (int j = 0;j<startNo-1;j++){
            first = first.getNext();
            helper = helper.getNext();
        }
        //开始报数时，将first和helper指针向后移动countNum-1次，然后first指向的节点出圈
        while (true){
            if (helper == first){   //当helper与first指向相同时，说明只剩一个节点了
                break;
            }
            for (int j = 0;j < countNum-1;j++){
                //将first和helper指针向后移动countNum-1次，然后first指向的节点出圈
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.println("此轮出圈的节点是："+first.getNo());
            //出圈操作
            first = first.getNext();    //类似于删除节点
            helper.setNext(first);
        }
        System.out.println("最后留在链表里的节点是："+first.getNo());
    }
}


class Boy {
    private int no; //编号
    private Boy next; //指向下一个节点，默认为null

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

    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;
    }

    @Override
    public String toString() {
        return "Boy{" + "no=" + no + '}';
    }
}

执行结果：