线性表环形单链表的约瑟夫问题如何实现实现

题目描述

设置编号为 1，2，3，…，n 的 n 个小孩围坐一圈，约定编号为 k（1<=k<=n）的小孩从 1 开始 报数，当数到 m 时对应的那个小孩出列。然后它的下一位又从 1 开始报数，当数到 m 时对应的小孩 又出列，以次类推，直到所有小孩出列为止，由此产生一个出队编号的序列。

例如，上图中从编号为 2 的小孩从 1 开始报数，每次数到 3 时对应的那个小孩就出列，最后得 到的出队编号就是：4、7、10、3、8、2、9、6、1、5。

package day03;

/**
* @Author yqq
* @Date 2022/05/06 17:36
* @Version 1.0
* 环形单链表的约瑟夫问题
*/
public class JosephTest {
public static void main(String[] args) {
//创建一个环形链表
Node lastNode = new Node(10);
Node node9 = new Node(9,lastNode);
Node node8 = new Node(8,node9);
Node node7 = new Node(7,node8);
Node node6 = new Node(6,node7);
Node node5 = new Node(5,node6);
Node node4 = new Node(4,node5);
Node node3 = new Node(3,node4);
Node node2 = new Node(2,node3);
Node headNode = new Node(1,node2);
lastNode.next = headNode;
joseph(headNode,lastNode,10,2,3);
}

/**
* 解决环形单链表的约瑟夫问题
* @param headNode 首节点
* @param lastNode 尾结点
* @param size 节点个数
* @param start 从编号为start的节点报数
* @param count 每次数几下
*/
public static void joseph(Node headNode,Node lastNode,int size,int start,int count){
//处理不合法的情况
//处理headNode为null的情况
if (headNode == null)
throw new NullPointerException("headNode is null:" + headNode);
//处理start和count不合法的情况
if (start < 1 || start > size || count <1)
throw new IllegalArgumentException("参数不合法");
//设置编号为start的节点开始报数，并且使用headNode指向该节点
//把headNode和lastNode往后移动start-1次
for (int i = 0; i < start - 1; i++) {
headNode = headNode.next;
lastNode = lastNode.next;
}
//定义一个循环，用于循环的执行报数操作
while (size != 0){//如果size等于0，则停止报数
//执行报数操作，也就是找到需要出圈的小孩，使用headNode节点指向需要出圈的节点
//把headNode和lastNode往后移动count-1次
for (int i = 0; i < count - 1; i++) {
headNode = headNode.next;
lastNode = lastNode.next;
}
//需要出圈的节点编号，也就输出headNode保存的数据值
System.out.print(headNode.data+"、");
//实现小孩的出圈操作，也就是把headNode从环形单链表中删除
//获得删除节点的后一个节点
Node nextNode = headNode.next;
//设置lastNode的next为nextNode
lastNode.next = nextNode;
//设置headNode的next值为null
headNode.next = null;
//更新size的值
size --;
//设置headNode指向nextNode
headNode = nextNode;
}
}
/**
* 节点类
*/
private static class Node{
/**
* 用于保存节点中的数值
*/
private Object data;
/**
* 用于保存下一个节点的地址值
*/
private Node next;

/**
* 专门为data做初始化的工作
* @param data
*/
public Node(Object data) {
this.data = data;
}

/**
* 专门为data和next做初始化的工作
* @param data
* @param next
*/
public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
}
}