Java数据结构Day8--单向环形链表(约瑟夫问题)

设编号为1,2,...n的n个人围成一个圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,他的下一位又从1开始报数,数到m的那个人又出列,依此类推,直到所有人出列位置,由此产生一个出队编号的序列

其实和之前的很多问题一样,一般就是考虑是否需要一个临时节点来辅助计算,如果需要,这个临时节点的位置应该在哪里?下面画了几张图来理解.

 上图是准备开始,这个k因为是1(从第一个人开始报数),所以first指针指向1

 因为m是2(报数从1到2),所以节点3需要出圈,这时候就要把节点2的next指向4,把节点3的next赋值给first(因为下一次报数要从节点4开始)

 如上图,就开始了第二次报数.

从这个流程中不难看出,一个节点X的出圈,必定是要将X的前一个节点的next指向X的next.

那我们怎么获得这个X的前一个节点呢?(在first指向节点X的情况下)

只能是使用到辅助节点,来记录要被删除的节点的上一个节点,来完整修改指针指向的操作.

接下来就是循环的编写问题了,谨慎一些即可

public class Josephu {
    public static void main(String[] args) {
        CircleSinglelinkedList circleSinglelinkedList = new CircleSinglelinkedList();
        int num = 5;
        int k = 1;
        int m = 2;
//        一共有num个人
//        约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,
//        他的下一位又从1开始报数,数到m的那个人又出列,依此类推
        circleSinglelinkedList.josephu(num,k,m);
    }
}
//创建一个单向环形链表队列
class CircleSinglelinkedList{
    // TODO: 2021/12/1 区分:first是头节点,在之前的单链表中的header是指向头结点
    private Man first = null;
    //创建链表
    public void create(int num){
        if (num < 1){
            System.out.println("编号不合法");
            return;
        }
        //创建一个临时变量,这个变量用来记录遍历到的节点
        Man tmp = null;
        //因为编号从1开始,所以i=1;i<=num
        for (int i = 1; i <= num; i++) {
            Man man = new Man(i);
            if (i == 1){
                //头结点需要单独拎出来
                first = man;
                first.setNext(man);
                tmp = first;
            }else{
                //tmp就是当前的最后一个节点
                //将tmp的next指向新节点
                tmp.setNext(man);
                //新节点的next指向头节点
                man.setNext(first);
                //将tmp变成最后一个节点,以供后续循环使用
                tmp = man;
            }
        }
    }
    //遍历链表
    public void show(){
        if (first == null){
            System.out.println("没有节点");
            return;
        }
        Man tmp = first;
        do {
            System.out.println(tmp);
            tmp = tmp.getNext();
            //当tmp等于first时,可以认定循环链表已经遍历完成,跳出循环
        } while (tmp != first);
    }
     TODO: 2021/12/1 解决约瑟夫问题
    public void josephu(int num, int k,int m) {
        int order = 1;
        create(num);
        //先找到开始的节点,但是要先进行一个合法性判断
        if (k > num || num < 1 || m < 0){
            System.out.println("参数非法");
            return;
        }
        Man tmp = first;
        do {
            tmp = tmp.getNext();
        }while (tmp.getNext() != first);
        //当tmp跳出循环时,就代表tmp已经是first后面的那个节点
        //至于为什么要拿到这个first后面的节点,后面就会知道了
        //报数前先将first指针指向开始节点,tmp指向开始的前一个节点
        for (int i = 0; i < k - 1; i++) {
            first = first.getNext();
            tmp = tmp.getNext();
        }
        //现在两个指针调整到位
        //开始报数
        //循环中止的条件是tmp和first都指向同一节点,即链表中只剩一个节点
        while (tmp != first) {
            for (int i = 0; i < m - 1; i++) {
                first = first.getNext();
                tmp = tmp.getNext();
            }
            //现在first指向的就是要出圈的人
            System.out.println("第" + order++ + "个出圈的是: 编号" + first.getNo());
            first = first.getNext(); //这个操作把first的下一节点赋值给了first
            tmp.setNext(first); //这个操作把出圈节点的前一个节点的next指向了first的位置
            //以上两行就相当于时删除节点的操作,应该很好理解
        }
        System.out.println("第" + order + "个出圈的是: 编号" + first.getNo());
    }

}
//创建一个man类,表示链表中的节点
class Man {
    private int no; //编号
    private Man next; //指向下一个节点
    //一个构造器
    public Man(int no){
        this.no = no;
    }
    //

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Man getNext() {
        return next;
    }

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

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