Use circular linked list to solve Josephus problem

Last updated on January 11, 2023 pm

[cited from wikipedia]Josephus Problem: A number of people are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.

The problem—given the number of people, starting point, direction, and number to be skipped—is to choose the position in the initial circle to avoid execution.

classCircleSinglyLinkedList { //initiate the first point privateNodefirst=newNode(-1);

//add nodes to the list publicvoidaddNode(int nums) { if (nums < 1) { System.out.println("nums should not be smaller than 1."); return; }

NodecurNode=null; for (inti=1; i <= nums; i++) { Nodechild=newNode(i); if (i == 1) { first = child; first.setNext(first); curNode = first; } else { curNode.setNext(child); curNode = child; child.setNext(first); } } }

//iterate the list publicvoidshowList() { //whether the list is empty if (first == null) { System.out.println("This list is empty."); return; }

NodecurNode= first; while (true) { System.out.println("The number of node is " + curNode.getNo()); if (curNode.getNext() == first) { break; } else { curNode = curNode.getNext(); } } }

/** * solve Josephus problem by Circle Single Linked List * 1、创建helper指针，开始时指向环形链表最后一个结点 * 2、开始count时，count m次即将first和helper同时移动m-1次 * 3、然后将数到的结点出列 * * @param startNo start from it * @param countNum every 'countNum' get one node * @param sum original number of nodes */ publicvoidjosephus(int startNo, int countNum, int sum) { if (first == null || startNo < 1 ||startNo>sum){ System.out.println("There's something wrong with the list or the augments."); return; }

//create a helper and point it to the last node Nodehelper= first; while (true){ if (helper.getNext() == first){ break; } helper = helper.getNext(); }

//move first and helper point to the startNo for (inti=0; i < startNo -1; i++){ first = first.getNext(); helper = helper.getNext(); }

//start the count process while (true){ //only one node left in the list if (helper == first){ break; }

for (inti=0; i <countNum-1; i++){ first = first.getNext(); helper = helper.getNext(); }

//get the 'first' node System.out.println("Get the '" + first.getNo() +"' node"); first = first.getNext(); helper.setNext(first); } System.out.println("The last node is " + first.getNo()); } }