One , Linked list

Ring linked list is another form of linked list storage structure , Its characteristic is that the pointer field of the last node in the table points to the head node , The whole list forms a ring .

Two , josephus problem

  Three , Create a circular list

1, The idea of constructing a one way circular linked list :

* Create the first node first , Give Way first Point to the node , And form a ring
* We didn't create a new node later , Add the current node to the existing ring list
2, Traversing ring linked list :

* Let's start with an auxiliary pointer ( ergodic )curBoy, point first node
* And then through a while Loop through the ring list =  first end
Four , Analysis on the problem of children out of the circle

Five , code implementation

1, Entity class
package com.guor.linkedlist.josepfu; public class Boy { private int no;
private Boy next;// Default empty public Boy(int no){ = no; } public int getNo() {
return no; } public void setNo(int no) { = no; } public Boy getNext() {
return next; } public void setNext(Boy next) { = next; } }
2, Ring linked list method class
package com.guor.linkedlist.josepfu; public class CircleSingleLinkedList {
// Create a first node , There is currently no number private Boy first = null; // Add child node , Build a ring list public void
addBoy(int nums){ //nums Do a data check if(nums<1){ System.out.println("nums The value of is incorrect .");
return; } // Auxiliary pointer , Construction of ring linked list Boy curBoy = null; // use for Loop to create a circular list for(int i = 1;i<=
nums;i++){ // Create child node by number Boy boy = new Boy(i); // The first child is special if(i==1){ first =
boy; first.setNext(first);// Form a ring curBoy = first;// Give Way curboy Point to the first child }else{
curBoy.setNext(boy); boy.setNext(first); curBoy = boy; } } } public void
showBoy(){ // Is the linked list empty if(first == null){ System.out.println(" The linked list is empty "); return; }
// because first Can't move , So use an auxiliary pointer to complete the traversal Boy curBoy = first; while(true){
System.out.printf(" The number of the child %d \n",curBoy.getNo()); if(curBoy.getNext() == first){
break; } curBoy = curBoy.getNext(); } } // Based on user input , Figure out the order of the children out of the circle public void
countBoy(int startNo,int countNum,int nums){ // check if(first == null || startNo<1
|| startNo>nums){ System.out.println(" Wrong parameter input , Please re-enter "); return; }
// Create secondary pointer , Help children out of the circle Boy helper = first; while (true){ if(helper.getNext() ==
first){ break; } helper = helper.getNext(); }
// join startNo no 1, Let's go first first and helper move k-1 second for (int i = 0; i < startNo - 1; i++) {
first = first.getNext(); helper = helper.getNext(); }
// Before children count , Give Way first and helper The pointer moves at the same time countNum second , And then out of the circle // Here is a loop operation , Until there is only one node in the circle
while(true){ if(helper == first){// Indicates that there is only one node in the circle break; }
// Give Way first,helper Move at the same time countNum- 1 for (int i = 0; i < countNum - 1; i++) { first =
first.getNext(); helper = helper.getNext(); } // This is first The node pointed to is the child node to be out of the circle
System.out.printf(" child %d Out of the circle \n",first.getNo()); // It's going to be first Point to the child node out of the circle first =
first.getNext(); helper.setNext(first); } System.out.printf(" The number of the last child left in the circle %d
\n",first.getNo()); } }
3, Test class
package com.guor.linkedlist.josepfu; public class Josepfu { public static void
main(String[] args) { // Is it necessary to build a circular list and traverse it OK CircleSingleLinkedList
circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5);// join 5 A child node circleSingleLinkedList.showBoy();
// Test children out of the circle circleSingleLinkedList.countBoy(1,2,5);//2,4,1,5,3 } }
Six , console output

©2019-2020 Toolsou All rights reserved,
Python Basic knowledge and notes Programmer Tanabata Valentine's Day confession code NOI2019 travels China's longest high speed rail officially opened ! The fastest way to finish the race 30.5 hour C Language programming to find a student's grade Software testing BUG describe ESP8266/ESP32 System : Optimize system startup time Unity Scene loading asynchronously ( Implementation of loading interface ) Baidu , Ali , Tencent's internal position level and salary structure , With job suggestions !PYTHON Summary of final review