//测试类
package Josephu; import java.util.Scanner; public class JosephuDemo { public static void main(String[] args) { Josephu j = new Josephu(); System.out.println("请输入参与人数:"); Scanner sc = new Scanner(System.in); int num = sc.nextInt(); System.out.println("请输入每个人的编号:"); for (int i = 0; i < num; i++) { int number = sc.nextInt(); j.addNode(number); } System.out.println("请输入初始位置:"); int first = sc.nextInt(); for (int i = 0; i < first-1 ; i++) { j.Head.next = j.Head.next.next; } System.out.println("请输入间隔数:"); int number = sc.nextInt(); JosephuCircle(j.Head,number); //System.out.println(j.Head.toString()); } public static void JosephuCircle (LinkNode Head, int number){ LinkNode l = null; LinkNode temp = Head.next; for(int i = 0;i < number-1; i++){ l = temp; temp = temp.next; } System.out.println("出局孩子编号:"); System.out.println(temp.toString()); if(temp == temp.next){ return; } l.next = temp.next; JosephuCircle(temp,number); } }
//结点类 package Josephu; public class LinkNode { public int number; public LinkNode next; public LinkNode(int number){ this.number = number; } @Override public String toString() { return "number:"+number ; } }
package Josephu; public class Josephu { LinkNode Head = new LinkNode(0); public void addNode (int number){ LinkNode l = new LinkNode(number); if(Head.next == null){ Head.next = l; l.next = Head.next; } LinkNode temp = Head.next; while(temp.next != Head.next){ temp = temp.next; } temp.next = l; l.next = Head.next; } public void show(){ LinkNode temp = Head.next; if(Head.next == null){ System.out.println("链表为空"); return; } while(temp != null){ System.out.println(temp.toString()); temp = temp.next; } } }
结果: