[数据结构与算法]环形链表操作及约瑟夫问题

环形链表操作及约瑟夫问题

单向环形链表：
约瑟夫问题：假设有n个人围成一圈，约定编号为k的人从1开始数数，数到m的那个人出列，他的下一个又从1开始数数，
数到m的人也出列，直到所有人都出列为止，由此产生一个出队编号的序列。
例如：
n = 5 5个人
k = 1 从第一个开始
m = 2 数到2就出列
1、2、3、4、5
1、2
出队列的编号为：2 剩余队列1、3、4、5并从3开始报1
3、4
出队列的编号为：4剩余队列1、3、5
5、1
出队列的编号为1 剩余队列3、5并从3开始报1
3、5
出队列的编号为5 剩余队列3，最后只有3出队列
因此出队列顺序为2、4、1、5、3

环形链表的实现思路：
1、创建一个实体类Boy，对应属性no编号、next下一个节点
2、先创建一个first节点编号随便给，后期第一个真正加入的节点编号覆盖它
3、当只有一个真正的节点时就自己和自己环形first = boy（1）；first.setnext（first）;
4、使用一个临时变量节点记录当前环形链表加入到最后的节点是什么，下次有节点接入时就在这个节点后面
5、temp = boy（1）；下一个接入时就temp.setnext（boy（2））;boy（2）.setnext（first）;temp=boy（2）；这样就加入了

约瑟夫问，根据输入个数生成一个小孩出圈顺序
思路：
1、创建一个辅助节点temp指向链表的最后一个节点，让小孩报数前将first和temp移动到报数小孩的节点和后一个节点
2、当小孩报数时，让first和temp同时移动，移动m-1次
3、这时就将first指向的节点出圈
4、出圈处理，先让first往前移动一次，然后temp的下一个节点指向移动后的first
下面是实现代码：

package com.ringList;

public class RingListDemo {
    /**
     * 环形链表
     */
    public static void main(String[] args) {
        RingList ringList = new RingList();
        ringList.addByNum(5);
        ringList.josephu(1,2,5);
        //ringList.addByNum(15);
       /* Boy boy1 = new Boy(1);
        Boy boy2 = new Boy(2);
        Boy boy3 = new Boy(3);
        Boy boy4 = new Boy(4);
        Boy boy5 = new Boy(5);
        ringList.addByBoy(boy1);
        ringList.addByBoy(boy3);
        ringList.addByBoy(boy4);
        ringList.addByBoy(boy2);
        ringList.addByBoy(boy5);
        ringList.show();*/
    }
}
//创建链表
class RingList{
    //创建一个first节点，默认先随意给编号，后期第一个节点值覆盖
    private Boy first = new Boy(-1);
    //记录最后一个加入的节点
    Boy temp = null;
    //添加节点,按输入数量创建环形链表
    void addByNum(int num){
        if (num<1){
            System.out.println("输入的数字不对");
            return;
        }
        //如果是第一个节点加入
        if (first.getNext()==null){
            //节点下标从1开始
            Boy boy = new Boy(1);
            //将boy(1)覆盖first，并自己环形起来
            first = boy;
            //自我环形起来
            first.setNext(first);
            //用临时变量记录最后添加的节点以便下一个节点加入时知道在谁后面
            temp = boy;
        }
        //其他的节点加入
        for (int i = 2;i<=num;i++){
            //创建节点
            Boy boy = new Boy(i);
            temp.setNext(boy);
            boy.setNext(first);
            temp = boy;
        }
        System.out.println("创建结束");
    }
    //传入节点参数添加链表
    void addByBoy(Boy boy){
        //如果是第一个节点加入
        if (first.getNext()==null){
            //将boy(1)覆盖first，并自己环形起来
            first = boy;
            //自我环形起来
            first.setNext(first);
            //用临时变量记录最后添加的节点以便下一个节点加入时知道在谁后面
            temp = boy;
        }else {
            temp.setNext(boy);
            boy.setNext(first);
            temp = boy;
        }
    }
    //遍历环形链表
    void show(){
        //先判断链表中有没有数据
        if (first.getNext()==null){
            System.out.println("链表数据为空");
            return;
        }
        //不为空的情况，由于first不能动，所以需借助 临时变量
        Boy temp = first;
        while (temp.getNext()!=null){
            //这里结束循环的条件是temp的下一个节点是first，因为遍历是从first开始的，
            //下一个节点是first的话说明就已经完成一圈遍历了
            System.out.println(temp);
            if (temp.getNext().equals(first)){
                break;
            }
            //往后移动一位
            temp = temp.getNext();
        }
    }
    /**
     * 约瑟夫问题，根据输入的链表个数，计算小孩出圈顺序
     * @param startNo 开始数数的小孩下标
     * @param count 表示数到几出圈
     * @param num 一个有几个小孩
     */
    void josephu(int startNo,int count,int num){
        if (first==null||startNo<1||num<startNo){
            System.out.println("输入的参数有误，请重新输入");
            return;
        }
        //创建临时节点,这时我们是没有办法知道first的后一个节点的需要循环处理
        Boy temp = first;
        while (true){
            if (temp.getNext().equals(first)){
                //说明临时节点已经移动到first的后一位了
                break;
            }
            temp = temp.getNext();
        }
        //移动临时节点和first节点到开始报数小孩的节点和后一个节点
        //例如：temp是0，first是1开始报数的小孩是3则应该移动到temp是2first是3的节点
        for (int i=0;i<startNo-1;i++){
            temp = temp.getNext();
            first = first.getNext();
        }
        //开始报数
        while (true){
            //圈中只有一个人的时候就结束循环
            if (temp.equals(first)){
                break;
            }
            //小孩移动count-1次,将first出圈，注意这里只能移动count-1次，因为本身自己也会报数
            for (int j=0;j<count-1;j++){
                temp = temp.getNext();
                first = first.getNext();
            }
            //这时first节点的小孩就是出圈的小孩节点
            System.out.println(first);
            //将其移除
            first = first.getNext();
            temp.setNext(first);
        }
        System.out.println("最后留在圈中的小孩是"+temp);
    }
}
//创建节点
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;
    }

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

以上代码是在跟着韩老师学习时，顺着韩老师提供的思路自己实现的，请大家多多指教！！！