Joseph Ring

This section begins with the Joseph problem
It is said that the famous Jewish historian Josephus had the following story: after the Romans occupied jotapat, 39 Jews hid in a cave with Josephus and his friends. 39 Jews decided that they would rather die than be caught by the enemy, so they decided a way of suicide. 41 people lined up in a circle, counting from the first person. Every time they counted to the third person, they had to commit suicide, Then count off again from the next until everyone commits suicide. However, Josephus and his friends did not want to comply. Start with one person, cross the k-2 person (because the first person has been crossed), and kill the K person. Then, he crossed the k-1 man and killed the k-th man. This process continues along the circle until there is only one person left, and the person can continue to live. The question is, given and, where to stand in the first place to avoid execution. Josephus asked his friend to pretend to obey first. He arranged his friend and himself in the 16th and 31st positions, so he escaped the death game.

Topic simplification
N people with numbers of 1, 2, 3, ·····, n sit around, report from the first person, the person who reports to m is listed, and then the next person listed starts to report from 1, and so on until everyone is listed.

Circular linked list

In the previous section, the one-way linked list we learned is to keep looking for nodes backward according to the next field until the next field of the last node is null; The circular linked list no longer has an end point, instead the last node points to the first node, so as to achieve the effect of circular operation. (as shown below)

It should be noted that when we have only one node, a single node should also be ring.

Thought analysis (creation and traversal of ring linked list)

First create the first node, let the first point to the node, and form a node ring. Then, when we do not create a new node, we can add the node to the original ring through operation

Code analysis (creation and traversal of ring linked list)

package datastructure;

public class linkedlist4 {
    public static void main(String[] args) {
        //Test the creation and display of ring linked list
        CircleList circleList=new CircleList();
        circleList.addBoy(25);
        circleList.showlist();
    }
}
//Create a circular one-way linked list
class CircleList{
    //Create a first node, which currently has no number
    private Boy first=null;
    //Add nodes and build a ring linked list
    public void addBoy(int nums){//Pass in a number directly, indicating how many nodes to add
        if (nums<1){
            System.out.println("nums The value of is incorrect");
        }
        //Use the for loop to create our circular linked list
        //Define a secondary node
        Boy curBoy=null;
        for (int i=1;i<=nums;i++){
            Boy boy=new Boy(i);
            if (i==1){//If it is the first node
                first=boy;//Make first point to the node
                first.setNext(first);//The next field points to itself to form a ring
                curBoy=first;//The secondary node used for the operation points to this node
            }else{//If not the first node
                curBoy.setNext(boy);//Point the next field of the previous node to the new node
                boy.setNext(first);//The next field of the new node points to the first node
                curBoy=boy;//Assign the new node to the auxiliary node, that is, the auxiliary node moves back
            }
        }
    }
    //Traverse the current circular linked list
    public void showlist(){
        //First judge whether the linked list is empty
        if (first==null){
            System.out.println("The linked list is empty and cannot be traversed");
            return;
        }
        //Because first always points to the first node, you need a secondary node to complete the traversal
        Boy curboy=first;
        while(true){
            System.out.printf("Node number is%d \n",curboy.getNo());
            if (curboy.getNext()==first){//Traversal completed
                break;
            }
            curboy=curboy.getNext();//Auxiliary node backward
        }
    }
}
//Create node Boy class
class Boy{
    private int no;
    private Boy next;
    public Boy(int no){
        this.no=no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public Boy getNext(){
        return next;
    }
    public void setNext(Boy next) {
        this.next = next;
    }
}

Train of thought analysis ring linked list extraction, Joseph Ring problem solution as an example)

Similarly, because first points to the first node, it will move when the node is taken out in order. Therefore, we still need auxiliary nodes to operate, so that the linked list is still a ring linked list after deleting nodes. When the corresponding node is taken out according to the topic order, the first also moves. Because the next reporting starts from the last bit of the extracted number, rather than the original first bit, the first points to the first node of the re reporting, that is, the last bit of the extracted number, rather than the original position.

Code analysis (extraction of ring linked list, Joseph Ring problem solution as an example)

package datastructure;

public class linkedlist4 {
    public static void main(String[] args) {
        //Test the creation and display of ring linked list
        CircleList circleList=new CircleList();
        circleList.addBoy(20);//Joseph's ring of 20 people
        //Start with the first person and count to three
        circleList.countBoy(1,3,20);
    }
}
//Create a circular one-way linked list
class CircleList{
    //Create a first node, which currently has no number
    private Boy first=null;
    //Add nodes and build a ring linked list
    public void addBoy(int nums){//Pass in a number directly, indicating how many nodes to add
        if (nums<1){
            System.out.println("nums The value of is incorrect");
        }
        //Use the for loop to create our circular linked list
        //Define a secondary node
        Boy curBoy=null;
        for (int i=1;i<=nums;i++){
            Boy boy=new Boy(i);
            if (i==1){//If it is the first node
                first=boy;//Make first point to the node
                first.setNext(first);//The next field points to itself to form a ring
                curBoy=first;//The secondary node used for the operation points to this node
            }else{//If not the first node
                curBoy.setNext(boy);//Point the next field of the previous node to the new node
                boy.setNext(first);//The next field of the new node points to the first node
                curBoy=boy;//Assign the new node to the auxiliary node, that is, the auxiliary node moves back
            }
        }
    }
    //Traverse the current circular linked list
    public void showlist(){
        //First judge whether the linked list is empty
        if (first==null){
            System.out.println("The linked list is empty and cannot be traversed");
            return;
        }
        //Because first always points to the first node, you need a secondary node to complete the traversal
        Boy curboy=first;
        while(true){
            System.out.printf("Node number is%d \n",curboy.getNo());
            if (curboy.getNext()==first){//Traversal completed
                break;
            }
            curboy=curboy.getNext();//Auxiliary node backward
        }
    }
    //According to the number of listed digits given as needed, output the listed order of people corresponding to each node
    public void countBoy(int startNo,int countNum,int nums){
        //startNo indicates the number of people to start counting
        //countNum indicates the number of digits to be listed
        //nums indicates how many people there are in the ring, that is, how many nodes there are
        if(first==null||startNo<1||startNo>nums){
            System.out.println("Incorrect input");
            return;
        }
        //Create an auxiliary node to form a ring
        Boy helper=first;
        //Loop the helper auxiliary node to the last node before starting
        while (true){
            if (helper.getNext()==first) {
                break;
            }
            helper=helper.getNext();
        }
        //First, move the first and helper to point to the first node and the last node respectively
        for(int j=0;j<startNo-1;j++){
            first=first.getNext();
            helper=helper.getNext();
        }
        //Move back first with the number of people in each position
        //It should be noted that because the first has pointed to the first person, the number of first mobile digits is one less than the number of people reporting
        while(true){
            if (helper==first){
                //Indicates that there is only one node in the ring
                break;
            }
            for (int j=0;j<countNum-1;j++){
                first=first.getNext();
                helper=helper.getNext();
            }
            System.out.println("Serial number is"+first.getNo()+"People in the queue");
            first= first.getNext();
            helper.setNext(first);//Delete node and form a ring
        }
        System.out.println("Serial number is"+first.getNo()+"The last one out");


    }


}
//Create node Boy class
class Boy{
    private int no;
    private Boy next;
    public Boy(int no){
        this.no=no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }
    public Boy getNext(){
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}