使用环形单向链表演示约瑟夫环问题Scala版本

思路

约瑟夫环问题 ： 题目是 假设有N个小朋友按顺序围成一圈，每个小朋友都有一个编号，假设从第m个小朋友从1开始报数，报到k的小朋友出圈，从出圈的下一个小朋友继续报数，重复上面的报数。直到所有的人出圈位置。 求出圈的小朋友的顺序是什么

解决方案： 我们使用的是单向的环形链表作为数据结构 思路大致分为

寻找指定开始节点跳动指定的步长-1（需要获取弹出节点的前一个节点，才可以做删除）显示弹出节点

代码

package com.xipenhui.cn import scala.collection.mutable.ArrayBuffer import scala.util.control.Breaks._ /** * 约瑟夫环问题 ： * 题目是 假设有N个小朋友按顺序围成一圈，每个小朋友都有一个编号，假设从第m个小朋友从1开始报数 * 报到k的小朋友出圈，从出圈的下一个小朋友继续报数，重复上面的报数。直到所有的人出圈位置。求出圈 * 的小朋友的顺序是什么 * 解决方案： * 我们使用的是单向的环形链表作为数据结构 */ object JosephuDemo { def main(args: Array[String]): Unit = { val josephu = new Josephu() val boys = josephu.addBoy(5) println("=======创建出来的boys是=======") josephu.show() println("===弹出小朋友===") josephu.popBoy(2,3,5) } } /** * 环形单向链表 * 1. 添加小孩子 * 2. 按照规则弹出小孩子 * 3. 显示环形队列的值，做过程校验 */ class Josephu { var head = Boy(-1) /** * * @param num 添加小孩的个数 */ def addBoy(num: Int) { //参数校验 if (num < 1) { throw new RuntimeException("input num must big than 1") } var currBoy: Boy = null for (i <- 1 to num) { val boy = new Boy(i) if (i == 1) { head = boy head.next = head currBoy = boy } else { currBoy.next = boy boy.next = head currBoy = boy } } } /** * 按照给定的规律弹出元素 * 1. 从开始数到第m个小朋友，拿到当前的小朋友 * 2. 在当前节点进行后移，移动到k个小朋友的前一个节点（单向链表删除需要使用前一个节点辅助） * 弹出当前小朋友，删除当前节点， * 3. 这里可以使用两个for循环， * 第一次循环的长度为链表长度 * 第二次循环的长度为移动的长度 k -1 (因为要前一个节点) * * @param startNum 从第num个位置开发数数字 * @param countNum 数数的长度为len * @param len 环形链表的长度 */ def popBoy(startNum: Int, countNum: Int, len: Int): Unit = { //val resArr = ArrayBuffer[Boy] if (head.next == null || startNum < 1 || startNum > len) { println("输入参数错误，请重新输入") System.exit(0) } var currBoy: Boy = head //可以找到起始位置的节点 breakable { while (currBoy.next != head) { if (currBoy.num == startNum) { break() } else { currBoy = currBoy.next } } } if (currBoy.next == head) throw new RuntimeException("can not find input element") //点名的次数为 len次 for (i <- 0 until len) { //从currBoy开始点名，点名的长度为countNum,这里是单向链表，要借助前一个节点进行删除 for (j <- 1 until countNum-1) { currBoy = currBoy.next } //这里 currBoy已经移动到需要移除节点的前一个节点 print(s"output element is ${currBoy.next.num} \n") currBoy.next = currBoy.next.next currBoy = currBoy.next } } //显示当前链表的内容 def show(): Unit = { var currBoy = head while (currBoy.next != head){ println(s"input boy's num is ${currBoy.num}") currBoy=currBoy.next } println(s"input boy's num is ${currBoy.num}") } } case class Boy(num: Int) { var next: Boy = null }