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為尾結點）