丢丢手绢-Scala实现单向循环链表（约瑟夫环）

package com.datacrafts.digitalevers.link

/**
 * 经典的约瑟夫环问题
 * 本质就是一个单向循环链表的实现
 * @param n 链表中初始节点个数
 */
class Josephus(n:Int) {
    var length = 0
    var head:node = null
    var curr:node = null
    var prev:node = null
    for(index <- 1 to n){
      if(length == 0){
        curr  = new node(index)
        prev = curr
        head = curr
        curr.next = curr
      } else {
        val temp  = new node(index)
        temp.next = head
        curr.next = temp
        prev = curr
        curr = temp
      }
      length += 1
    }
    //初始化完成后复位
    curr = head
    prev = head

  /**
   * 移动到第k个人
   * 1 <= k <= length
   */
  def moveToK(k:Int): Unit ={
      for(index <- 1 until k){
          prev = curr
          curr = curr.next
      }
  }

  /**
   * 开始丢手绢过程
   * 丢到第 m 个人则退出
   * 若curr 与 prev相等 说明循环链表中只剩一个节点 则结束循环
   */
  def circle(m:Int): Unit ={
    while(curr != prev){
      for(index <- 1 until m){
        prev = curr
        curr = curr.next
      }
      //循环结束 删除当前节点
      println(curr.id)
      prev.next = curr.next
      curr = curr.next
      length -= 1
    }
    println(curr.id)
  }

  /**
   * 展示约瑟夫环上所有节点数据
   */
  def show(): Unit = {
    var curr = head
    for(index <- 1 to length){
      println(curr.id)
      curr = curr.next
    }
  }
}

/**
 * 节点类型
 * @param _id
 */
class node(_id:Int){
  var id:Int = _id
  var next:node = null
}

object Josephus{
  def main(args: Array[String]): Unit = {
    var josephus = new Josephus(7)
    //josephus.show()
    josephus.moveToK(4)
    //println(josephus.curr.id)
    //println(josephus.prev.id)
    josephus.circle(3)
    //println(josephus.length)
  }
}