I have to write a program that gives the output of the last man standing, according to the Josephus problem, utilizing a circular list. It seems to work the majority of the time, However, when I enter a series 7(people) 1(starting position), 3(kill count). It gets thrown off half way through the killing.(approximately when the list is 2357) I have looked through the code several times following the numbers and cannot figure out why in this iteration it kills 3 instead of 5.
import java.util.Scanner;
class Link{
public int itemData;
public Link next;
public Link(int itemNumber){
//initialize's data
itemData = itemNumber;
}
public void displayLink(){
System.out.print("{" + itemData + "}");
}
}
class LinkList{
private Link first; //first link
private Link last;
private Link current;
public LinkList getCurrent;
public LinkList(){
first = null;
last = null;
current = null;
}
public boolean isEmpty(){
return(first == null);
}
public void setCurrent(){
current = current.next;
}
public Link getCurrent(){
return current;
}
public void fillList(int listSize){
for(int i=1; i < listSize + 1; i++){
Link newLink = new Link(i);
if(isEmpty()){
first = newLink;
current = first;
}
else{
current.next = newLink;
newLink.next = first;
last = newLink;
setCurrent();
}
}
}
public Link find(int holder, int listSize){
Link marker = first;
for(int i = 0; i < listSize; i++){
if(marker.itemData == holder){
break;
}
else{
marker = marker.next;
}
}
return marker;
}
public void deleteEvery(int holder, int pass, int listSize){
while(listSize!= 1){
Link current = find(holder, listSize);
Link previous = first;
for(int i = 1; i < pass; i++){
current = current.next;
}
previous = current;
current = current.next;
if(current == first){
first = first.next;
}
else{
previous.next = current.next;
}
holder = current.next.itemData;
displayList(--listSize);
}
}
public void displayList(int listSize){
System.out.print("List:");
Link current = first;
for(int i = 1; i < listSize+1; i++){
current.displayLink();
current = current.next;
}
System.out.print("");
}
}
class Josephus{
public static void main(String[] args){
LinkList people = new LinkList();
Scanner input = new Scanner(System.in);
System.out.print("Please enter 3 integers (size, holder, passing).");
int listSize = input.nextInt();
int holder = input.nextInt();
int pass = input.nextInt();
people.fillList(listSize);
people.displayList(listSize);
people.deleteEvery(holder, pass, listSize);
}
}
Nevermind I figured it out in the deleteEvery() function my if statement also needed to follow through with the deletion of the position, it was changing the first element and the continuing to the next iteration.