1. Member Join Date
Nov 2013
Posts
3
Rep Power
0

## Joesphus Problem

I'm trying to work with the Josephus Problem of continually removing an element until one remains through a circular Linked List. I am lost of how to remove the element though. I keep getting NullPointerExceptions and I do not know why.

For my version of the Josephus, I use int elements
such as

1 2 3 4 5 6
and let's remove every second element until 1 remains
4 5 6 1 2
1 2 4 5
5 1 2
5 1
1
element 1 is the remainder.

I am able to add all elements, but removing is the difficulty.
Java Code:
```/**
* Prisoner is a class that is used for a linked list
* of prisoners.  The linked list is
* circular where the tail points back to the head.
*/
//import java.util.Iterator;
class Prisoner{

class DigitNode
{
public int num=0;			// Digit's position in line
public DigitNode next=null;	// Reference to next Digit
/**
* Digit constructor, initializes number
*/

public DigitNode(int number)
{
//
num = number;
next = null;
}

public String toString() {
return "" + num;
}

}

private int digit;
private DigitNode tail = null;	// Tracks end of list as it is constructed

/**
* constructs a circular linked list of
* @param n DigitNode, current is the first DigitNode and tail is the last DigitNode(next of tail is current)
*/

public Digi(int n)
{
//
digit= n;
tail = null;
}

DigitNode newNode = new DigitNode(n);
}

/*
* prints all Digit starting from current until tail
*/
@Override
public String toString()
{
//
String strVal = "";
Digit p = new Digit(digit);

for (int i = digit; i >= 1; i--) {
}
while (position != null) {
strVal = strVal + position.num + " ";
//System.out.println(strVal);
position = position.next;
}
return strVal;
}

/**
* moves the current
* @param n positions
*/
public void move(int k)
{
//
while (current.num != k) {
current = current.next;
}
}
/*
* call move(k) and then remove the digit in current position
*/
public void eliminate(int k)
{
//

move(k);
DigitNode previous = tail;

while (current.num != k) {
previous = current;
current = current.next;
}
if ( current == head) {
} else {
previous.next = current.next;
}

}

}```
Last edited by MitchellWall; 11-20-2013 at 10:04 PM. Reason: added [code] ... [/code] tags  Reply With Quote

2. Member Join Date
Nov 2013
Posts
3
Rep Power
0

## Re: Joesphus Problem

Thank you for adding code tags, now I know how to do that JosAH.  Reply With Quote

3. Member Join Date
Nov 2013
Posts
3
Rep Power
0

## Joesphus Problem

I'm trying to work with the Josephus Problem of continually removing an element until one remains through a circular Linked List. I am lost of how to remove the element though. I keep getting NullPointerExceptions and I do not know why.

For my version of the Josephus, I use int elements
such as

1 2 3 4 5 6
and let's remove every second element until 1 remains
4 5 6 1 2
1 2 4 5
5 1 2
5 1
1
element 1 is the remainder.

I am able to add all elements, but removing is the difficulty.
Java Code:
```/**
* Prisoner is a class that is used for a linked list
* of prisoners.  The linked list is
* circular where the tail points back to the head.
*/
//import java.util.Iterator;
class Prisoner{

class DigitNode
{
public int num=0;			// Digit's position in line
public DigitNode next=null;	// Reference to next Digit
/**
* Digit constructor, initializes number
*/

public DigitNode(int number)
{
//
num = number;
next = null;
}

public String toString() {
return "" + num;
}

}

private int digit;
private DigitNode tail = null;	// Tracks end of list as it is constructed

/**
* constructs a circular linked list of
* @param n DigitNode, current is the first DigitNode and tail is the last DigitNode(next of tail is current)
*/

public Digi(int n)
{
//
digit= n;
tail = null;
}

DigitNode newNode = new DigitNode(n);
}

/*
* prints all Digit starting from current until tail
*/
@Override
public String toString()
{
//
String strVal = "";
Digit p = new Digit(digit);

for (int i = digit; i >= 1; i--) {
}
while (position != null) {
strVal = strVal + position.num + " ";
//System.out.println(strVal);
position = position.next;
}
return strVal;
}

/**
* moves the current
* @param n positions
*/
public void move(int k)
{
//
while (current.num != k) {
current = current.next;
}
}
/*
* call move(k) and then remove the digit in current position
*/
public void eliminate(int k)
{
//

move(k);
DigitNode previous = tail;

while (current.num != k) {
previous = current;
current = current.next;
}
if ( current == head) {
} else {
previous.next = current.next;
}

}

}```  Reply With Quote

4. Senior Member Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Re: Joesphus Problem

I am assuming you mean removing an item in a linked list.

In a circular linked list, the tail points back to the head. So to delete an item, save the parent of the item you want to delete. Now you have parentOfItem so you just need to have parentOfItem.child = item.child. And the link is deleted. When item.child = item, the node points to itself, so you are done since you only have one item remaining.

Regards,
Jim  Reply With Quote

5. ## Re: Joesphus Problem

If I remove every second element from the circular list (1, 2, 3, 4, 5, 6) I get (1, 3, 5); I don't understand your result ...

kind regards,

Jos  Reply With Quote

6. ## Re: Joesphus Problem

What happened to this thread? There's a 'soft link', pointing to the same thread; one of the links states that the thread was moved ... it's bitrot, I'm telling you ...

kind regards,

Jos

ps. I don't dare to remove one of the 'links'.  Reply With Quote

7. Just a guy Join Date
Jun 2013
Location
Netherlands
Posts
5,114
Rep Power
13

## Re: Joesphus Problem

... I have no idea what you're talking about here! I see nothing wrong.  Reply With Quote

8. ## Re: Joesphus Problem

Don't you see two (identical) threads 'Josephus Problem' and one of them seems to be moved; they're both one thread only ...

kind regards,

Jos  Reply With Quote

9. ## Re: Joesphus Problem

i use arraylists remove method.. and make sure you have the right index

im removing from a list here Lists

its also supposed to be a countdown too zero  Reply With Quote

circular, josephus, linked, list, problem 