本文共 3024 字，大约阅读时间需要 10 分钟。

单向环形链表

约瑟夫问题

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

n = 5即有五个人

k=1，从第一个人开始

m=2，数两下

出队列的顺序是 2——4—–1—–5——-3

思路

1.先创建第一个节点，让我们的first指向该节点，并形成环形

2.后面当我们创建一个新的节点，就把该节点，加入到已有的环形链表中

遍历环形链表

先让一个辅助指针(变量)，指向first节点

然后通过一个while循环遍历改环形链表即可当：curBoy.next = first结束

出圈思路

1.需要创建一个辅助指针(变量)helper,事先应该指向环形链表的最后这个节点

当然，我们要小孩报数前，让first和helper移动k-1次，移动到k那个地方

2.当我们的小孩报数时，我们的first和helper同时移动m-1次

3.将我们first指向的小孩 节点出圈

​ first = first.next;

​ helper.next = first;

原来first指向的节点，就没有任何引用了，就会被回收

代码实现

package com.wang.linkedlist;/** * @author 王庆华 * @version 1.0 * @date 2020/12/9 21:07 * @Description TODO * @pojectname 算法代码 */public class Josepfu {       public static void main(String[] args) {           CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();        circleSingleLinkedList.addBoy(5);//加入五个小孩//        circleSingleLinkedList.showBoy();        circleSingleLinkedList.countBoy(1,2,5);    }}//创建环形单向链表class CircleSingleLinkedList{       //创建我们的第一个节点,当前还没有编号    private Boy first = null;    //添加小孩节点，构建成环形链表    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;//让我们的curBuy指向第一个小孩            }else {                   curBoy.setNext(boy);//将我们原来指向第一个节点指向现在新加的节点                boy.setNext(first);//我们新加的节点的next节点指向第一个                curBoy = boy;//我们的辅助节点指针，移到我们新加的节点上            }        }    }    /**     * 遍历我们的环形链表     */    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();//curBoy向后面移动        }    }    //根据用户的输入，计算小孩的出圈顺序    /**     *     * @param startNo   表示从第几个小孩开始报数     * @param countNum  表示我们一次数几下，一次报几个数     * @param nums      表示最初有多少个小孩在圈中     */    public void countBoy(int startNo,int countNum,int nums){           //先对数据校验        if (first == null || startNo < 1||startNo>nums){               System.out.println("参数输入有误，请重新输入");            return;        }        //创建辅助指针，帮助我们的小孩出圈        Boy helper = first;        //需要创建一个辅助指针(变量)helper,事先应该指向环形链表的最后这个节点        while (true){               if (helper.getNext() == first){                   break;            }            helper = helper.getNext();//往下走        }        //小孩报数前，让first和helper移动k-1次，移动到k那个地方        for(int j =0;j

转载地址：http://ooik.baihongyu.com/