Java 约瑟夫环（循环链表解决）

问题描述：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。

解题思路:因为是围成一圈，所以用循环链表是最符合相关思维的（不是最优解），对于第M个人进行出队，然后前后节点连接起来继续形成闭环（新约瑟夫环）

代码（Java版）

import java.util.Scanner;


/**
 * @author : jeasion
 * @name
 * @comment
 * @return
 */
public class practice37 {
	public static void main(String[] args) {
		int N = 0;
		int M = 0;
		Scanner s = new Scanner(System.in);
		System.out.print("N:");
		N = s.nextInt();
		System.out.print("M:");
		M = s.nextInt();
		Josephus josephus = new Josephus();
		josephus.dead(M, N);
	}

}

class Josephus {
	int person;
	Josephus next;
	Josephus pointer;//用于出队第M人

	public void dead(int m, int n) {
		int M = m;
		int N = n;
		Josephus josephus = new Josephus();
		pointer = josephus;
            
                //构建循环链表
		for (int i = 0; i < N; i++) {
			josephus.person = i;
			josephus.next = new Josephus();
			josephus = josephus.next;
		}
		josephus = pointer;
		while (josephus.next.next != null) {
			josephus = josephus.next;
		}
		josephus.next = pointer;

		int count = m - 1;
		System.out.print("死亡名单：");
		while(!pointer.next.equals(pointer)) {
			count--;
			Josephus before = pointer; //记录出队前的人，便于以后使其指向M+1的人
			pointer = pointer.next;
			if (count == 0) {
				System.out.print(pointer.person + "  ");
				before.next = pointer.next;
				pointer.next = null;                                                               
				pointer = before.next;
				count = m - 1;
			}
		}
		System.out.println("\n幸存者："+pointer.person);
	}

}