java单项环形链表

2022-08-21 11:04:29

Josephu（约瑟夫环，约瑟夫）问题

在学习环形链表之前我们先了解一下约瑟夫问题，设编号为1，2，3……n。的n个人围坐一圈约定编号为k（1<=k<=n）的人从1开始报数，当数到m的那个人出列，后一个人在从1开始报数，以此类推直到最后移入出列。由此产生一个出列编号顺序。

提示：用一个不带头结点的循环链表来处理约瑟夫问题，先构成一个有n个节点的单循环链表，然后由k从1开始计数，到m时，对应的节点从链表中移除，然后被删除的节点的后一位又从1开始报数，直到最后一个节点。

和我们小时候玩的丢手绢一样

单项环形链表图例：

单项环形链表的实现思路：

创建环形链表

1.先创建第一个节点，让first指向该节点，并让第一个节点的next指向自己形成环形。

2.后面每当加入一个新的节点就把该节点加入到已有的环形链表中即可

遍历环形链表

1.先让一个辅助指针（变量）curBoy,指向first节点

2.然后通过一个while循环遍历该环形链表即可，cueBoy.next = first 代表着结束

代码实现：

1.创建一个小孩类，一个小孩代表一个节点

//创建一个boy类，代表一个节点
class Boy{
    private int no;//小孩编号
    private Boy next;//指向下一个节点，默认为null
    public Boy(int no){
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

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

    public int getNo() {
        return no;
    }

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

2.创建一个单项环形链表类

class CircleSingleLinkList{
    //创建一个first节点，但不先辅助
    private Boy first = null;
｝

3.创建添加节点的方法

 /**
     * 添加小孩节点、创建一个环形链表
     * @param nums
     */
    public void addBoy(int nums){
        //nums代表有多少个小孩节点
        //先做数据有效判断
        if(nums<1){
            System.out.println("nums的值不正确");
            return;
        }
        Boy curBoy = null;//辅助节点帮助创建环形链表
        //使用for来创建环形链表
        for(int i = 1;i<=nums;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;
            }
        }
    }

4.创建遍历节点的方法

 /**
     * 遍历当前链表
     */
    public void showBoy(){
        //判断链表是否为空
        if(first == null){
            System.out.println("没有任何节点");
            return;
        }
        //因为first不能动，因此我们创建一个辅助节点
        Boy curBoy = first;
        while (true){
            System.out.println("编号："+curBoy.getNo());
            if (curBoy.getNext() == first){//说明已经遍历完成
                break;
            }
            curBoy = curBoy.getNext();
        }
    }

效果展示：

 //测试环形链表
        CircleSingleLinkList cir = new CircleSingleLinkList();
        cir.addBoy(6);
        cir.showBoy();

编号：1
编号：2
编号：3
编号：4
编号：5
编号：6

码农公寓