编号是1，2...n的n个人围坐一圈，编号为k（1<=k<=n）的人从1开始报数，每数到第m个，该人就要离开此圈，它的下一位从1开始报数，数到m出列，这样依次下来，直到圈中所有人出列，最后产生一个出队编号。
目录
一、首先编写一个节点类
public class Node {
//节点编号(题中人的编号)
private int id;
//下一个节点
private Node next;
public Node(int id) {
this.id = id;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return "Node{" +
"id=" + id +
'}';
}
}二、问题解决思路
定义一个头节点，不代表题中任何人的编号；
- 添加节点；
- 查看环形链表中的所有节点；
- 根据题意，编写对应代码。
省略代码在第三部分
public class CSLinkedList {
//头节点，编号不计算
public Node first = new Node(-1);
/**
* 为环形链表添加节点
* @param num 环形链表的节点个数
*/
public void addNode(int num){
//代码
}
/**
* 查看环形链表中所有的节点
*/
public void showNode(){
//代码
}
/**
* 约瑟夫环问题
* @param start 开始报数人的编号：编号为k（1<=k<=n）的人从1开始报数
* @param count 离开时报的数：每数到第m个，该人就要离开此圈，它的下一位又从1开始报数
* @param num 圈内人数：编号是1，2...n的n个人围坐一圈
*/
public void josephCircle(int start, int count, int num){
//代码
}
}
三、省略部分对应代码
1、添加节点
/**
* 为环形链表添加节点
* @param num 环形链表的节点个数
*/
public void addNode(int num){
//判断num
if (num < 1){
System.out.println("不符合要求！");
return;
}
//临时节点
//添加临时节点，只用更改临时节点指向的节点即可，不需要对环形链表中的节点进行复杂操作
Node temp = null;
for (int i = 1; i <= num; i++) {
//新节点
//从编号1开始，每循环一次，添加一个新节点
Node node = new Node(i);
//判断添加方式
if (i == 1){
//第一个节点的添加
//使编号为1的节点为第一个节点，第一个节点的下一个节点指向自身。
first = node;
first.setNext(first);
//使编号为1的节点指向临时节点，方便以后的添加操作
temp = first;
}else {
//其它节点的添加
//使临时节点指向新添加的节点
temp.setNext(node);
//新添加的节点指向编号为1的节点
node.setNext(first);
//使新添加的节点指向临时节点，方便以后操作
temp = node;
}
}
}2、查看环形链表中的所有节点
public void showNode(){
if (first.getNext() == null){
System.out.println("该环形链表为空！");
return;
}
Node node = first;
while (true){
//输出每一个节点的编号
System.out.printf("编号为%d\n",node.getId());
//节点的下一个节点指向第一个节点时，循环结束
if(node.getNext() == first){
break;
}
//使节点向后移动
node = node.getNext();
}
}3、约瑟夫环问题相关代码
public void josephCircle(int start, int count, int num){
//判断输入是否正确
if (first == null || start < 1 || count > num){
System.out.println("输入有错误！");
return;
}
//定义一个结束节点，指向环形链表的最后一个元素
Node end = first;
while (end.getNext() != first){
end = end.getNext();
}
//定义一个开始节点
//开始报数人的编号为2,则first节点移动2-1次
//first节点移动，结束节点（end）也会移动，移动次数和first节点相同
for (int i = 0; i < start - 1; i++) {
first = first.getNext();
end = end.getNext();
}
//出列节点
//判断节点个数，只有一个节点
while (end != first){
//判断出列节点
//报3的人出列，first是编号为2的人，则移动3-1次，编号为4的人出列，
for (int i = 0; i < count - 1; i++) {
first = first.getNext();
end = end.getNext();
}
System.out.printf("编号-%d-节点出环形链表！\n",first.getId());
first = first.getNext();
end.setNext(first);
}
System.out.printf("编号-%d-节点出环形链表！\n",first.getId());
}四、测试代码
public class Test01 {
public static void main(String[] args) {
Node node1 = new Node(1);
CSLinkedList list = new CSLinkedList();
list.addNode(15);
list.showNode();
System.out.println("-------------------");
list.josephCircle(1,2,15);
}
}测试结果如下：
这是我在书里面看的，书名记不太清，看到就是缘分！
互联网时代，我们即将看到，无创造则无毁灭。
以上仅供学习参考，可能会有不正确的地方，不过问题应该不大吧，注释是我的想法，表述可能有一点点粗糙，希望可以帮助大家！
