Java實現循環列表解決約瑟夫環問題

約瑟夫環：共有n個人圍成一圈，從1開始報數，數到m的人出圈，求最後幸運者序號？？

下面用Java實現循環列表解決這個問題：

package com.iteye.ljmdbc7a;

import java.util.Scanner;

/**
 * 循環列表的Java實現，解決約瑟夫環問題
 * @author LIU
 *
 */
public class LinkedList
{
 //定義結點，必須是static
 static class Node
 {
  int data;
  Node next;
  Node(int arg1)
  {
   this.data = arg1;
  }
 }
 public static void main(String[] args)
 {
  int n = 0,m = 0;//定義總人數n，和出圈數字m
  //輸入n和m
  System.out.println("輸入總人數n，出圈數字m");
  Scanner scanner = new Scanner(System.in);
  n = scanner.nextInt();
  m = scanner.nextInt();
 
  //初始化循環列表,頭結點first和尾結點p
  Node first = new Node(1);
  first.next = first;
  Node p = first;
  for(int i=2; i<=n; i++)
  {
   Node temp = new Node(i);
   temp.next = p;
   p.next = temp;
   p = p.next;
  }
  p.next = first;//尾接頭形成循環鏈表（p為尾結點）
 
  //執行出圈操作
  System.out.println("出圈順序為:");
  while(p != p.next)
  {
   //下面for循環後，p是第m個結點的前一個結點
   for(int i=1; i<m; i++)
    p = p.next;
   //刪除第m個結點
   System.out.print(p.next.data+" ");
   p.next = p.next.next;
  }
  System.out.print("\n幸運者是:"+p.data);
 }
 
}

注意42行->>>>p.next = first;//尾接頭形成循環鏈表（p為尾結點）