Java使用单链表实现约瑟夫环

本文实例为大家分享了Java使用单链表实现约瑟夫环的具体代码，供大家参考，具体内容如下

构建一个单向的环形链表思路

1.先创建第一个节点, 让first指向该节点, 并形成环形
2.后面当我们每创建一个新的节点, 就把该节点加入到已有的环形链表中即可.

遍历环形链表思路

1.先让一个辅助指针(变量)curBoy, 指向first节点
2.然后通过一个while循环遍历该环形链表即可 curBoy.next == first 结束

生成小孩出圈顺序的思路

1.根据用户的输入, 生成一个小孩出圈的顺序

n = 5, 即有 5 个人
k = 1, 即从第1个人开始数数
m =2, 每次进行数两下

2.需求创建一个辅助指针(变量)helper, 事先应该指向环形链表的最后这个节点

3.在小孩报数前, 让first 指针和 helper指针分别指向正确的位置, 即需要移动 k-1次

4.在小孩报数时, 每次让first指针和helper指针移动 m-1次

5.此时 first指针 指向的节点就是出圈的节点

代码实现

first = frist.getNext();
helper.next = first;

由于first指向的节点数就没有任何引用, 就会被回收

package com.beyond.linkedlist;

import org.omg.CORBA.PUBLIC_MEMBER;

public class Josepfu {
public static void main(String[] args){
 CircleSingleLinkedList name = new CircleSingleLinkedList();
 name.addBoy(5);
 name.showBoy();
 name.countBoy(1, 2, 5);
}

}

//创建一个环形的单向链表
class CircleSingleLinkedList {
// 创建一个first节点,当前没有编号的
private Boy first = new Boy(-1);

// 添加小孩节点,构成一个环形的链表
public void addBoy(int nums) {
 if (nums < 1) {
  System.out.println("nums 的值不正常");
  return;
 }
 Boy curBoy = null; // 辅助指针,帮助构造环形链表
 // 使用for来创建我们的环形链表
 for (int i = 1; i <= nums; i++) {
  // 根据编号,创建小孩节点
  Boy boy = new Boy(i);
  // 如果是第一个小孩
  if (i == 1) {
   first = boy;
   first.setNext(first);
   curBoy = first;
  } else {
   curBoy.setNext(boy);
   boy.setNext(first);
   curBoy = boy;
  }

}

}

// 遍历当前的环形链表
public void showBoy() {
 if (first == null) {
  System.out.println("没有小孩!");
  return;
 }
 // 因为first不能动, 因此我们仍然使用一个辅助指针完成遍历
 Boy curBoy = first;
 while (true) {
  System.out.printf("小孩的编号％d \n", curBoy.getNo());
  if (curBoy.getNext() == first) {
   break;
  }
  curBoy = curBoy.getNext(); // 后移
 }
}

// 根据用户的输入,计算出小孩出圈的顺序
/**
 *
 * @param startNo  表示从第几个小孩开始数数
 * @param countNum 表示数几下
 * @param nums     表示最初有多少个小孩在圈子中
 */
public void countBoy(int startNo, int countNum, int nums) {
 if (first == null || startNo < 1 || startNo > nums) {
  System.out.println("输入数据有误~");
  return;
 }
 // 创建所需要的辅助指针,帮助小孩出圈
 Boy helper = first;
 // 需求创建一个辅助指针helper, 事先指向该环形列表的最后这个节点
 while (true) {
  if (helper.getNext() == first) {
   break;
  }
  helper = helper.getNext();
 }

//小孩报数前,将指针移动到各自开始的位置,移动 k-1 次
 for (int i = 0; i < startNo-1; i++) {
  first = first.getNext();
  helper = helper.getNext();
 }

//当小孩报数时, 让first 和 helper 指针同时移动 m-1次, 然后出圈
 //这是一个循环操作,直到圈中只剩下一个小孩为止
 while (true) {
  if (helper == first) {
   break;
  }
  for (int i = 0; i < countNum-1; i++) {
   first = first.getNext();
   helper = helper.getNext();
  }
  System.out.printf("小孩％d出圈!\n",first.getNo());
  first = first.getNext();
  helper.setNext(first);
 }
 System.out.printf("最后留在圈中的小孩编号为:％d",first.getNo());
}

}

//先创建一个Boy类, 表示一个节点
class Boy {
private int no;
private Boy next;

public Boy(int no) {
 this.no = no;
}

public int getNo() {
 return no;
}

public void setNo(int no) {
 this.no = no;
}

public Boy getNext() {
 return next;
}

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

}

来源：https://beyond.blog.csdn.net/article/details/109607293