约瑟夫环使用单向环形链表解题约瑟夫环又称丢手绢是一个非

约瑟夫环又称丢手绢是一个非常有名的数学问题，它规定一个环形链表中从N的位置开始第M个Node被删除，直到元素内没有元素，算出它们的删除顺序。
【约瑟夫环使用单向环形链表解题】首先我们做一个环形链表，也就是lastNode.next=fristNode 。将链表变成一个环。其实这题使用双向环形链表最简单，但往往面试题要求使用单向链表。
文章插图
package com.dfsn.cloud.eureka;public class AnnulusLinkedList {// 头节点private Node frist;// 元素个数private int size;public void add(T t) {// 添加第一个元素时，它的下一个指向它自己if (frist == null) {Node newNode = new Node(t, null);frist = newNode;newNode.next = frist;} else {Node newNode = new Node(t, null);Node temp = frist;// 如果Node.next是first说明它是最后一个节点了，在它后边添加while (temp.next != frist) {temp = temp.next;}// 既然找到了最后一个，就将新创建的添加到最后一个的末尾temp.next = newNode;// 最后新添加Node.next指向fristnewNode.next = frist;}size++;}// 获取长度public int size() {return size;}// 约瑟夫环又称丢手绢杀人游戏// 从链表的start位置开始数countNum个位置并且删除该位置的Node// 其实这个题用双向环形链表的难度会低一点，只要做一个计数器 l ，递增l并且不断地node.next// l==countNum后删除该node即可具体做法如下两行代码// node.prev.next=node.next// node.next.prev=node.prev// 然后重置l ，继续自增查询。// 但是如果是单向环形链表就要考虑一个问题，当l==countNum时，该如何删除这个元素？// 单向链表无法自己删除自己，只能通过上级删掉自己。问题是，单向链表又没有prev// 所以这需要我们维护两个node ，一个是frist ，两一个是last,last.next就是frist 。// 也就是当l满足条件后， frist=frist.next;last.next=frist;// 然后重置l ，继续自增查询。public void josehu(int start, int countNum) {if (size == 0) {throw new RuntimeException("没有元素无法计算");}if (countNum < 1) {throw new RuntimeException("countNum不能小于1");}if (start < 1) {throw new RuntimeException("start不能小于1");}if (start > size) {throw new RuntimeException("start位置不能大于" + size);}// 首先找到最后一个节点，最后一个节点的条件就是它的next==fristNode last = this.frist;while (true) {if (last.next == this.frist) {break;} else {last = last.next;}}// 第一个节点就是fristNode frist = this.frist;// 因为要从start位置开始数数，所以要找到start// frist和last要同时向前移动，但last始终在frist前边for (int i = 1; i < start; i++) {frist = frist.next;last = last.next;}// 计数器int l = 1;while (true) {// 如果==1说明就剩下一个Node就停止，最后把它自杀就行if (size == 1) {break;} else {if (l == countNum) {// 如果l==countNum表示当前frist要被杀掉System.out.println(frist.item);// frist的下一个成为新的fristfrist = frist.next;// last的下一个还是fristlast.next = frist;// 重置计数器l = 1;size--;} else {// 如果l!=countNum那么把计数器+1 ， frist和last同时向后偏移frist = frist.next;last = last.next;l++;}}}// 打印最后一个元素System.out.println(frist.item);// 置为null表示自杀frist = null;size--;}// 查看链表public void show() {Node temp = frist;while (true) {System.out.println(temp);temp = temp.next;if (temp.next == frist) {System.out.println(temp);break;}}}// 节点对象class Node {private T item;private Node next;public Node(T item, Node next) {this.item = item;this.next = next;}@Overridepublic String toString() {return "Node [item=" + item + "]";}}}public static void main(String[] args) {AnnulusLinkedList annulusLinkedList = new AnnulusLinkedList<>();annulusLinkedList.add("A");annulusLinkedList.add("B");annulusLinkedList.add("C");annulusLinkedList.add("D");annulusLinkedList.add("E");annulusLinkedList.add("F");annulusLinkedList.add("G");annulusLinkedList.add("H");annulusLinkedList.josehu(2, 2);}