算法面经---单向循环链表（解决约瑟夫问题）

单向循环链表--解决约瑟夫问题

一、单向循环链表的应用场景

1.1 问题描述

Josephu(约瑟夫、约瑟夫环) 问题 Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数 到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由 此产生一个出队编号的序列。 提示：用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结 点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直 到最后一个结点从链表中删除算法结束。

1.2 问题化简

Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

n = 5 , 即有5个人 k = 1, 从第一个人开始报数 m = 2, 数2下

单向循环链表1.png

出圈的顺序 2->4->1->5->3

二 单向循环链表的实操

2.1 首先节点创建

// 创建一个boy类，表示一个节点
 class Boy {
  private int no;
  private Boy next;// 指向下一个节点，默认为null
 ​
  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;
  }
 ​
 }

2.2 单向循环链表的添加（构建）

创建环形链表的思路图解

单向循环链表2.png

1. 先创建第一个节点, 让 first 指向该节点，并形成环形

2. 后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可.

 class CircleSingleLinkedList{
  //创建一个first节点，当前没有编号
  private Boy first = null;

  //添加一个小孩节点，构建成为一个环形的链表
  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;     //让curBoy指向第一个小孩
  }else{
  curBoy.setNext(boy);
  boy.setNext(first);
  curBoy = boy;   //curBoy永远紧跟当前链表中的最新节点
  }
  }
  }
 }

2.2 遍历单向循环链表

 //遍历当前的环形链表
  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();
  }
  }

2.3 小孩出圈问题分析

单向循环链表3.png

根据用户的输入，生成一个小孩出圈的顺序 n = 5 , 即有5个人 k = 1, 从第一个人开始报数 m = 2, 数2下

1. 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点. 补充： 小孩报数前，先让 first 和 helper 移动 k - 1次

2. 当小孩报数时，让first 和 helper 指针同时 的移动 m - 1 次

3. 这时就可以将first 指向的小孩节点 出圈 first = first .next helper.next = first 原来first 指向的节点就没有任何引用，就会被回收

出圈的顺序 2->4->1->5->3

代码实现：

 // 根据用户的输入，计算出小孩出圈的顺序
  /**
  * 
  * @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){  //说明helper指向最后小孩节点
  break;
  }
  helper = helper.getNext();
  }
  //小孩报数前，先让 first 和  helper 移动 startNo - 1次
  for(int j=0;j<startNo-1;j++){
  first = first.getNext();
  helper = helper.getNext();
  }
  //当小孩报数时，让first 和 helper 指针同时 的移动  countNum  - 1 次, 然后出圈
  //这里是一个循环操作，知道圈中只有一个节点
  while(true){
  if(helper == first){
  break;
  }
  //让first和helper指针同时的移动countNum-1
  for(int j=0;j<countNum-1;j++){
  first = first.getNext();
  helper = helper.getNext();
  }
  //这时first指向的节点，就是要出圈的小孩节点
  System.out.printf("小孩%d出圈\n", first.getNo());
  //这时将first指向的小孩节点出圈
  first = first.getNext();
  helper.setNext(first); //
  }
  System.out.printf("最后留在圈中的小孩编号%d \n", first.getNo());
  }