Joseph’s problem (circular linked List)

Problem description

There are n children, numbered from 1 to N, counting from the first person, reporting from 1, reporting from m will be out, and then from the m+1 person, repeat the above process. At the end of the game, ask the n children in what order?

The solution

(1) Use ring single linked list to solve this problem. First, connect n nodes together to form a ring linked list. Start with the first node, delete the node when counting to M, and count again until only the last node is left in the list. At this point, the last node is still a ring, so it can still count up to M, which is the last exit. (2) the use of array simulation solution (3) the use of recursive methods to solve the circular single linked list.

Code Implementation (Java)

So if you create a singly linked list, you add one node to make a ring, or you add all the nodes to make a singly linked list, and then you connect the first node to the last node.

package com.Josephu;

public class Josephu {
    public static void main(String[] args) {
        JosephuLinkedList jList = new JosephuLinkedList(5);
        jList.josephuList();
        jList.showJosephuList();
        jList.JossephuGame(2); }}class Children {
    private int no;
    private Children next;

    public Children (int no) {
        this.no = no;
    }

    public int getNo(a) {
        // Get the number
        return no;
    }

    public Children getNext(a) {
        // Get the next Children node
        return next;
    }

    public void setNext(Children next) {
        // Set the next Children node
        this.next = next; }}class JosephuLinkedList {
    Children first = null;
    / / total number of Children
    private int sum;
    public JosephuLinkedList (int sum) {
        this.sum = sum;
    }
    // Set a circular list based on the total number of people
    public void josephuList (a) {
        Children currentChild = null;
        for(int i = 1; i <= sum; i++) {
            Children child = new Children(i);
            if (i == 1) {
                first = child;
                first.setNext(first);
                currentChild = first;
            } else{ child.setNext(first); currentChild.setNext(child); currentChild = child; }}}// Iterate over the circular list
    public void showJosephuList (a) {
        Children currentChild = first;
        System.out.println("The numbers in the circular list are :");
        while(currentChild.getNext() ! = first) { System.out.println(currentChild.getNo()); currentChild = currentChild.getNext(); } System.out.println(currentChild.getNo()); }// Count the queue sequence,count is the number of people count out, starting from 1
    public void JossephuGame (int count) {
// int j =0;
        Children helper = first;
        Children currentChild = first;
        while(helper.getNext() ! =first) { helper = helper.getNext(); }// while ( j ! = sum-1) {you can also use this as a loop condition
        System.out.println("Queue exit child number is :");
        while (true) {
            for (int i = 1; i <= count - 1; i++) {
                currentChild = currentChild.getNext();
                helper = helper.getNext();
            }
// j++;
            System.out.println(currentChild.getNo());
            currentChild = currentChild.getNext();
            helper.setNext(currentChild);
            if (currentChild == helper) {
                // There is only one person left in the team
                break; } } System.out.println(currentChild.getNo()); }}Copy the code