方法一、自定义的链表实现
package com.code.yuesefu;
public class YueSeFuList {
public static void main(String[] args) {
int count = 41;//申请一个指定长度的链表
Node n = YueSeFuList.createNodes(count);
for(int i=0;i<count;i++){
Node second = n.next;//第2个
n = n.next.next;//第3个
System.out.println(n.item);//返回第3个
second.next = n.next;//让第2个的next指向第4个
n = n.next;//让第4个作为第1个
}
}
public static Node createNodes(int count){
Node next = null;
Node head = new Node<String>("head",null);
Node last = head;//刚开始头和尾都是同一个元素
//新元素插入尾部，新元素作为尾
for(int i=1; i<=count; i++){
next = new Node<String>("num "+i,null);
last.next = next;
last = next;
}
last.next = head.next;//最后把尾部元素和插入的第一个元素连起来
head = head.next;//把刚开始的那个head去掉，让插入的第一个元素作为head，返回出去
return head;
}
private static class Node<E>{
E item;
Node<E> next;
//Node<E> prev;
Node( E element, Node<E> next) {
this.item = element;
this.next = next;
// this.prev = prev;
}
}
}
方法2、使用LinkedList实现
package com.code.yuesefu;
import java.util.LinkedList;
import java.util.List;
/*
* 约瑟夫问题
* 41个人，围成圈，从第一个人开始从1报数，当碰到3时，那个人出局。然后后面的人再从1开始报数，直到全部出局
据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人(因为第一个人已经被越过)，并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
* */
public class YueSeFu {
public static void main(String[] args) {
List list = new LinkedList<String>();
//初始化链表
for(int i=0;i<41;i++){
int a = i+1;
list.add("p"+a);
}
int i = 0;
while(list.size() > 2){
i = i+2;//每次移动2位，如果位置超出链表长度，就从头再来
if(i>list.size()-1){
i = i-list.size();
}
System.out.println((String)list.remove(i));
}
//最后的两个幸存者
System.out.println(list.get(0));
System.out.println(list.get(1));
}
}