链表应用----约瑟夫问题

一、题目

二、思路分析

可以看做是两步：创建环形链表和出圈

 三、代码实现

public class Josepfu {
    public static void main(String[] args) {
        CircleSingleLinkedList list = new CircleSingleLinkedList();
        list.add(5);
//        list.show();
        list.countBoy(1,2,5);
    }
}

class CircleSingleLinkedList{
    // 创建一个first节点,当前没有编号
    private Boy first = null;

    public void add(int nums){
        if (nums < 0){
            throw new RuntimeException("输入有误");
        }
        Boy temp = null;
        for (int i=1;i<=nums;i++){
            Boy boy = new Boy(i);
            if (i == 1){
                first = boy;
                first.setNext(first);
                temp=first;
            }else{
                temp.setNext(boy);
                temp = boy;
                boy.setNext(first);
            }
        }
    }

    public void show(){
        if (Objects.isNull(first)){
            throw new RuntimeException("连表为空");
        }
        Boy boy = first;
        while (true){
            System.out.println("小孩"+boy.getNo());
            if (boy.getNext() == first){
                break;
            }
            boy = boy.getNext();
        }
    }

    public void countBoy(int start,int count,int nums){
        if (start <1 || Objects.isNull(first) || start>nums){
            throw new RuntimeException("输入有误");
        }

        // 1.创建一个辅助指针
        Boy help = first;
        // 2.让help 指向最后一个节点
        while (true){
            if (help.getNext() == first){
                break;
            }
            help = help.getNext();
        }
        // 3.小孩报数前让first与help 节点向前移动start -1个位置，如果start 为1的话就不用移动，原因在于first本来就在第一位，而help本来就在最后以为
        // help一直都是在first的后一位
        for (int i =0;i<start-1;i++){
            first=first.getNext();
            help = help.getNext();
        }

        // 4.出圈
        while (true){
            // 4.1 help一直都是在first后面，当help等于first时，说明只有一个节点
            if (help == first){
                break;
            }
            /** 4.2 将两个指针移到指定位置；比如说：原本first是在第一个节点，help是在first后面，也就是最后一个节点。
                现在要从第二个节点开始。那么first和help就要往前移动一位；
             */
            for (int j = 0;j<count-1;j++){
                first = first.getNext();
                help = help.getNext();
            }
            System.out.println("出圈小孩"+first.getNo());
            // 4.3 此时的first是要出圈的节点，所以这个时候呀first指针要下移一位。
            first =first.getNext();
            // 4.4 然后help连接first，也就是出圈节点的下一位。这个时候出圈节点就没有指针和连接指向他了，垃圾回收器就回对他进行回收
            help.setNext(first);
        }
        // 5.打印最后一个节点
        System.out.println("最后一个小孩"+first.getNo());

    }

}

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

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