Java用单向环形链表来解决约瑟夫环Josepfu问题

简单介绍

如果把单链表的最后一个节点的指针指向链表头部，而不是指向NULL，那么就构成了一个单向循环链表，通俗讲就是让尾节点指向头结点。

单向环形链表应用场景：Josephu(约瑟夫、约瑟夫环)问题：
设编号为1, 2, … n的n个人围坐一圈，约定编号为k (1<=k<=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

代码实现

节点类

//节点类
class JNode {
   private int id;
   private JNode next;

public JNode(int id) {
       this.id = id;
   }

public int getId() {
       return id;
   }

public JNode getNext() {
       return next;
   }

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

}

链表类（包括节点管理和约瑟夫环问题解决）

//链表类
class CircleSingleLinkedList {
   private JNode first = null; //定义第一个节点，未创建时为null

//添加节点，构建环形链表
   public void add(int num) {
       if (num < 1){
           System.out.println("创建个数不符合规定！");
           return;
       }
       JNode curNode = null; //辅助变量
       for (int i = 1; i <= num; i++) {
           JNode newNode = new JNode(i);
           if (i == 1){ //第一个节点较为特殊
               first = newNode; //真正创建了第一个节点
               first.setNext(first); //形成环状
               curNode = first; //让辅助变量开始作用
           }else { //第二个及其之后节点
               curNode.setNext(newNode); //让当前节点指向新建的节点
               newNode.setNext(first); //让新建的节点指向第一个节点，形成环状
               curNode = newNode; //更新辅助变量
           }
       }
   }

//遍历链表
   public void list(){
       if (first == null){
           System.out.println("链表为空！");
           return;
       }
       JNode temp = first;
       while (true){
           System.out.printf("取出节点％d\n",temp.getId());
           if (temp.getNext() == first){ //说明已经遍历到最后一个了
               break;
           }
           temp = temp.getNext();
       }
   }

//根据参数让节点出圈（Josepfu）
   public void josepfu(int startNode,int count,int num){ //startNode为开始的那个节点，count为每次数第几个，num为链表节点个数
       if (first == null || startNode < 1 || count < 1 || startNode > num){
           System.out.println("链表为空或者输入的参数不符合标准！");
           return;
       }
       //让first移动到startNode指定的节点，即移动startNode-1次
       for (int i = 0; i < startNode - 1; i++) {
           first = first.getNext();
       }
       //创建一个辅助变量，让其指向最后一个节点（first前一个）
       JNode helper = first;
       while (helper.getNext() != first){
           helper = helper.getNext();
       }
       //开始按照要求出圈，每次都让helper和first移动count-1次
       while (true){
           if (helper == first){ //圈中只剩下一个节点
               break;
           }
           for (int i = 0; i < count - 1; i++) {
               first = first.getNext();
               helper = helper.getNext();
           }
           //此时first指向的即为要出圈的节点
           System.out.printf("节点％d出圈\n",first.getId());
           //将出圈的节点从链表中移除
           first = first.getNext();
           helper.setNext(first);
       }
       System.out.printf("节点％d为最后一个节点",first.getId());
   }
}

测试类

/**
* @Author: Yeman
* @Date: 2021-10-15-22:33
* @Description:
*/
public class JosepfuTest {
   public static void main(String[] args) {

CircleSingleLinkedList linkedList = new CircleSingleLinkedList();

linkedList.add(5);

linkedList.list();
       System.out.println("===================");

linkedList.josepfu(1,2,5);
   }
}

来源：https://blog.csdn.net/m0_46653805/article/details/120791745