约瑟夫环又称丢手绢是一个非常有名的数学问题，它规定一个环形链表中从N的位置开始第M个Node被删除，直到元素内没有元素，算出它们的删除顺序。
首先我们做一个环形链表，也就是lastNode.next=fristNode。将链表变成一个环。其实这题使用双向环形链表最简单，但往往面试题要求使用单向链表。
package com.dfsn.cloud.eureka; public class AnnulusLinkedList<T> { // 头节点 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指向frist newNode.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==frist Node last = this.frist; while (true) { if (last.next == this.frist) { break; } else { last = last.next; } } // 第一个节点就是frist Node 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的下一个成为新的frist frist = frist.next; // last的下一个还是frist last.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; } @Override public String toString() { return "Node [item=" + item + "]"; } } }
public static void main(String[] args) { AnnulusLinkedList<String> 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); }