Joseph’s ring is a very famous mathematical problem, which specifies that the MTH Node in a circular list should be deleted from position N until there are no elements in it, and calculate the order in which they are deleted.

First let’s make a circular list, which is lastNode.next=fristNode. Turn a linked list into a ring. In fact, this question is the easiest to use a two-way circular list, but often interview questions require the use of a one-way list.

 

 

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 = newNode (T, null); // If (frist == null) {Node newNode = newNode (T, null); frist = newNode; newNode.next = frist; } else { Node newNode = new Node(t, null); Node temp = frist; // If Node.next is first, it is the last Node. Add while (temp.next! = frist) { temp = temp.next; } temp. Next = newNode; temp. Next = newNode; Newnode. next = frist; newNode.next = frist; } size++; } public int size() {return size; } // Count countNum from the start of the list and delete nodes from that position // Next =node.next // node.next. Prev =node.prev // then reset l, Continue to increment the query. // If l==countNum, how do I delete this element? // A list cannot delete itself, it can only be deleted by its parent. The problem is, one-way lists don't have prev // so we need to maintain two nodes, one for frist and two for last and last.next is frist. // frist=frist.next; last.next=frist; // Then reset l to continue incrementing the query. Public void josehu(int start, int countNum) {if (size == 0) {throw new RuntimeException(" no elements can be counted "); } if (countNum < 1) {throw new RuntimeException("countNum must not be less than 1"); } if (start < 1) {throw new RuntimeException("start must not be less than 1"); } if (start > size) {throw new RuntimeException("start position cannot be greater than "+ size); } next==frist Node last = this.frist; while (true) { if (last.next == this.frist) { break; } else { last = last.next; } // The first Node is frist Node frist = this.frist; For (int I = 1; for (int I = 1; i < start; i++) { frist = frist.next; last = last.next; } // count int l = 1; While (true) {// If (size ==1) {break; } else {if (l ==countNum) {// If l==countNum indicates that the current frist is to be killed system.out.println (frist. Item); // Next frist becomes new frist frist = frist.next; Last = frist; // Last = frist; // set count l = 1; size--; } else {// if l! Frist = frist. Next; countNum =count +1, frist = frist. last = last.next; l++; }}} // Prints the last element system.out.println (frist.item); 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; }} // Node object 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 + "]"; }}}Copy the code

View Code

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);
    }
Copy the code

View Code