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

first = frist.getNext();
helper.next = 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(); // 后移
  }
 }

 // 根据用户的输入,计算出小孩出圈的顺序
 
 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;
 }

}