Realization of Joseph Ring of javascript Cyclic Linked List

Preface

Legend has it that during the Jewish War in the 1st century AD, Jewish historian Flavio Josephus and his 40 compatriots were surrounded by Roman soldiers. Jewish soldiers decided to commit suicide rather than be prisoners, so they negotiated a suicide plan. They form a circle, starting with one person, killing the third person when counting to the third person, and then counting again until everyone is killed. Joseph and another man decided not to take part in this crazy game. They quickly calculated two positions and stood there to survive. Write a program to circle n individuals, and the first m individuals will be killed. Calculate which two people will survive in the last circle. Use a circular linked list to solve this problem.

Seeing this problem, the first thing that comes to mind is to use a circular linked list, and to calculate how many elements there are in the linked list, which are very important. Then there is finding the current node and moving m nodes forward in the linked list. The following 11 analysis: Loop linked list is easy to achieve, is the initialization of the first node of the linked list next point to itself, so initialize a null node, note that the head of the linked list is not a node. It is written as follows: this.head.next = this.head; Calculating how many elements there are in the list is also very simple, just find the head node, and then go down until you return to the head node again

The code is as follows:

var node = this.head;
var i = 0;
while (!(node.next.element == "head")){
 node = node.next;
 i++;
}
return i;

When initializing the linked list, we define a current node and assign it as the head node this.currentNode = this.head; So that you can use it to point to the next 1 node when moving a node. When moving a node forward, there is a place to pay attention to. If you currently move to the head node, you need to move another node forward this.currentNode.next.next .

The code is as follows:

while (n>0){
 if(this.currentNode.next.element == "head"){
 this.currentNode = this.currentNode.next.next;
 }else{
 this.currentNode = this.currentNode.next;
 } 
 n--;
}

Code implementation

/**
 *  Using circular linked list to solve Joseph ring problem 
 * */

// Linked list node 
function Node(element){
 this.element = element;
 this.next = null;
}

// Defining linked list classes 
function LList(){
 this.head = new Node("head");
 this.head.next = this.head;
 this.find = find;
 this.insert = insert;
 this.findPrevious = findPrevious;
 this.remove = remove;
 this.currentNode = this.head;
 // Move forward from the current node of the linked list n Nodes 
 this.advance = advance; 
 // How many elements are there in the current linked list 
 this.count = count;
 this.display = display;
}

// Find Node 
function find(item){
 var currNode = this.head;
 while (currNode.element != item){
 currNode = currNode.next;
 }
 return currNode;
}

// Insert a new node 
function insert(newElement, item){
 var newNode = new Node(newElement);
 var current = this.find(item);
 newNode.next = current.next;
 current.next = newNode;
}

// Find the top of the current node 1 Nodes 
function findPrevious(item){
 var currNode = this.head;
 while (!(currNode.next == null) && (currNode.next.element != item)){
 currNode = currNode.next;
 }
 return currNode;
}

// Remove the current node 
function remove(item){
 var prevNode = this.findPrevious(item);
 if(!(prevNode.next == null)){
 prevNode.next = prevNode.next.next;
 }
}

// Move forward n Nodes 
function advance(n){
 while (n>0){
 if(this.currentNode.next.element == "head"){
  this.currentNode = this.currentNode.next.next;
 }else{
  this.currentNode = this.currentNode.next;
 } 
 n--;
 }
}

// How many elements are there in the current linked list 
function count(){
 var node = this.head;
 var i = 0;
 while (!(node.next.element == "head")){
 node = node.next;
 i++;
 }
 return i;
}

// Output all nodes 
function display(){
 var currNode = this.head;
 while (!(currNode.next == null) && !(currNode.next.element == "head")){
 document.write(currNode.next.element + " ");
 currNode = currNode.next;
 }
}

var person = new LList();
person.insert('1','head');
person.insert('2', '1');
person.insert('3', '2');
person.insert('4' , '3');
person.insert('5' , '4');
person.insert('6' , '5');
person.insert('7' , '6');
person.insert('8' , '7');
person.insert('9' , '8');
person.insert('10' , '9');


person.display();
document.write('<br>');


var n = 3;
while (person.count() > 2){
 person.advance(n);
 person.remove(person.currentNode.element);
 person.display();
 document.write('<br>');
}

Here we assume that there are 10 people, and every time we count to the third person, this person commits suicide, and the final output is as follows:

In the end, Joseph and his companions stood at the fourth and tenth of the team, leaving only the two of them. I don't know if this happened in history. If it happened, Joseph is really a genius to solve this problem in such a short time. I don't know if he used pointers to solve this problem at that time or used ordinary array recursion to solve it.

Summarize

The above is the whole content of this article. I hope the content of this article can bring 1 certain help to everyone's study or work. If you have any questions, you can leave a message for communication.