Java用单向环形链表来解决约瑟夫环Josepfu问题
作者:叶绿体不忘呼吸 时间:2023-03-13 18:54:20
简单介绍
如果把单链表的最后一个节点的指针指向链表头部,而不是指向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
标签:Java,单向环形链表,约瑟夫环,Josepfu
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Java四种权限修饰符知识点详解
2023-11-11 06:12:59
Java 如何使用Feign发送HTTP请求
2023-05-10 15:04:08
Java基于HttpClient实现RPC的示例
2023-10-29 15:55:02
spring+html5实现安全传输随机数字密码键盘
2023-04-05 13:46:39
![](https://img.aspxhome.com/file/2023/7/125587_0s.jpg)
Springboot集成graylog及配置过程解析
2023-06-18 17:15:02
![](https://img.aspxhome.com/file/2023/7/64167_0s.png)
详解SpringBoot统一响应体解决方案
2023-03-08 08:54:13
java垃圾回收原理之GC算法基础
2023-10-05 16:10:09
![](https://img.aspxhome.com/file/2023/2/87352_0s.png)
Java数组高级算法与Arrays类常见操作小结【排序、查找】
2022-12-02 15:17:14
![](https://img.aspxhome.com/file/2023/3/78263_0s.png)
Java详细分析LCN框架分布式事务
2022-10-17 15:49:08
![](https://img.aspxhome.com/file/2023/2/130012_0s.png)
MyBatisPlus+Lombok实现分页功能的方法详解
2021-07-04 06:34:57
![](https://img.aspxhome.com/file/2023/3/85483_0s.png)
android实现蓝牙app代码
2021-07-08 07:52:15
maven profile实现多环境配置的示例
2023-09-24 12:02:57
![](https://img.aspxhome.com/file/2023/3/64513_0s.png)
详解java倒计时三种简单实现方式
2023-11-11 16:47:38
![](https://img.aspxhome.com/file/2023/8/62508_0s.png)
Eclipse快速添加get、set方法的操作技巧
2022-11-20 04:11:59
![](https://img.aspxhome.com/file/2023/7/78937_0s.jpg)
关于Mybatis-Plus Wrapper是否应该出现在Servcie类中
2023-11-28 22:04:56
web压力测试工具_动力节点Java 学院整理
2022-03-25 00:48:21
![](https://img.aspxhome.com/file/2023/8/132328_0s.png)
mybatis-plus生成mapper扩展文件的方法
2023-08-10 07:29:05
![](https://img.aspxhome.com/file/2023/4/58044_0s.png)
Android ActionBar搜索功能用法详解
2023-01-24 21:15:02
经典实例讲解C#递归算法
2022-04-11 22:34:16
![](https://img.aspxhome.com/file/2023/2/94552_0s.gif)
浅谈Java 类中各成分加载顺序和内存中的存放位置
2022-12-23 17:24:23