/**
* 题目：
* 环形单链表约瑟夫问题
* 据说著名犹太历史学家Josephus有过以下故事：在罗马人占领乔塔帕特后，39个犹太
*入与 Josephus及他的朋友躲到一个洞中， 39个犹太人决定宁愿死也不要被敌人抓到，于是
*决定了一个自杀方式，41个人排成一个圆圈，由第 1个人开始报数，报数到 3的人就自杀，
*然后再由下一个人重新报 1, 报数到 3 的人再自杀， 这样依次下去， 直到剩下最后一个人
*时， 那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表
*描述该结构并呈现整个自杀过程。
* 要求：
* 输入： 一个环形单向链表的头节点head和报数的值m。
* 返回： 最后生存下来的节点， 且这个节点自己组成环形单向链表， 其他节点都删掉。
* 分析：
* 1.如果链表为空或者链表节点数为 1, 或者 m的值小于 1, 则不用调整就直接返回。
* 2.在环形链表中遍历每个节点，不断转圈， 不断让每个节点报数。
* 3.当报数到达 m时， 就删除当前报数的节点。
* 4.删除节点后，别忘了还要把剩下的节点继续连成环状， 继续转圈报数， 继续删除。
* 5.不停地删除， 直到环形链表中只剩一个节点， 过程结束。
*
* @author 雪瞳
*
*/
*代码
public class Node {
public int value;
public Node next;
public Node(int data) {
this.value=data;
}
}
public class JosephusKill {
private int count=0;
private Node last = null;
public Node josehusListKill(Node head ,int m) {
if(head.next == head || m<1 || head ==null) {
return head;
}
//构造环形链表
last = head;
while(last.next != head) {
last = last.next;
}
while(head != last) {
count++;
if(count == m) {
//删除节点
last.next=head.next;
count = 0;
}else {
last = last.next;
}
head = last.next;
}
return head;
}
}
import java.util.Random;
import java.util.Scanner;
public class TestJosephusKill {
public static void main(String[] args) {
JosephusKill kill = new JosephusKill();
TestJosephusKill test = new TestJosephusKill();
//获取初始信息
Random rand = new Random();
Scanner sc = new Scanner(System.in);
System.out.println("请输入链表长度");
int K = sc.nextInt();
System.out.println("请输入报数的数值");
int m = sc.nextInt();
//随机生成链表
Node nodes[]=new Node[K];
for(int i=0;i<nodes.length;i++) {
nodes[i]=new Node(rand.nextInt(20)+1);
}
for(int i =0;i<nodes.length-1;i++) {
nodes[i].next=nodes[i+1];
}
nodes[nodes.length-1].next=nodes[0];
Node head = nodes[0];
//test
test.showNode(head,K);
Node reverseNode = kill.josehusListKill(head, m);
test.showNode(reverseNode,1);
}
public void showNode(Node head,int k) {
if(k==1) {
System.out.println("活下来的是： "+ head.value);
}else {
System.out.println("链表内的元素如下所示...");
int i = 0;
while(head != null) {
if(i==k) {
break;
}else {
i++;
System.out.print(head.value+"\t");
head = head.next;
}
}
System.out.println();
}
}
}
原文：https://www.cnblogs.com/walxt/p/12538949.html