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

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.printOTOuGAmoUln("链表为空或者输入的参数不符合标准！");

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);

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。