单向环形链表应用场景

单向环形链表应用场景 约瑟夫问题

Josephu(约瑟夫、约瑟夫环) 问题

Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

注：丢手帕问题

解题思路

1、新建一个环线链表，实现链表的增查功能

2、设计出圈顺序，使用helper作为辅助指针，协助取消指针引用

代码实现

package com.qf.linkedList;

public class Josefu {
    public static void main(String[] args) {
        CircleLinkedList circleLinkedList=new CircleLinkedList();
        circleLinkedList.add(600);
        circleLinkedList.list();
        circleLinkedList.countBoy(50,20,600);
    }
}

class CircleLinkedList{
    private Boy first=new Boy(-1);

    //添加
    public void add(int num){
        if (num<1){
            System.out.println("输入的数据有误，请重试~~~");
            return;
        }

        Boy curBoy=null;
        for (int i = 1; i <= num; i++) {
            Boy boy=new Boy(i);
            if (i==1){
                //第一个元素成为了队头，并循环
                first=boy;
                first.setNext(first);
                curBoy=first;
            }else{
                boy.setNext(first);
                curBoy.setNext(boy);
                curBoy=boy;
            }
        }
    }

    public void countBoy(int startNo,int countNums,int nums){
        //从startNo开始数数 ，countNums表示的是步长，nums代表的是总共的长度
        if (first==null||startNo<1||countNums>nums){
            System.out.println("输入的数据有误，请重新输入");
        }

        Boy helper=first;
        //1、找到helper的位置，它在first的前一个位置
        while (true){
            if (helper.getNext()==first){
                break;
            }
            helper=helper.getNext();
        }

        //2、让first、helper移动到指定的位置startNo，需要移动startNo-1下
        for (int i=0;i<startNo-1;i++){
            first=first.getNext();
            helper=helper.getNext();
        }

        //3、让小孩报数，移动first和helper的指针,移动countNums-1下
        while (true){
            if (first==helper){
                break;
            }

            for (int j = 0; j < countNums-1; j++) {
                first=first.getNext();
                helper=helper.getNext();
            }
            System.out.println("出圈的编号为："+first.getNo());
            first = first.getNext();
            helper.setNext(first);

        }

        System.out.println("组后出圈的编号为："+first.getNo());

    }

    //展示
    public void list(){
        Boy temp=first;
        while (true){
            System.out.println(temp);
            if (temp.getNext()==first){
                break;
            }
            temp=temp.getNext();
        }
    }
}
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 +
                '}';
    }
}