# Solve Josephus Problem using Linked List

In this article, we will see how to solve the Josephus Problem using a linked list. First, let’s learn what Josephus’s problem is. Suppose `n` people are standing in a circle. Every person except one will get executed. In each turn, the `kth` person gets executed. This process continues until one person remains. Moreover, the counting starts at some person in the circle and then continues in a specific direction. The problem here is to find the position of the person that lives.

## A solution to Josephus Problem using Linked List

Let’s take an example to clarify the problem.

As you can observe from the above illustration, we can quickly solve this problem using a circular linked list. Initially, we create a linked list with `n` nodes, where each node contains the index/ position as its value. Note that we are using `0` based indexing. In the beginning, the start variable will be equal to the head node, i.e., the first node inserted into the linked list. We will perform the following steps until the linked list contains only a single node:

• Get the kth node in the linked list starting from the start node.
• Update the start variable to be equal to the node after the kth node.
• Remove the kth node from the linked list.

Finally, when the last node remains, we return its value as the person’s position that lives.

### Implementation

The code for the circular linked list and the Josephus problem is given below:

```#node for the linked list
class Node:
def __init__(self, value=None, next=None):
self.value = value
self.next = next #reference to the next node

#implementation of linked list for the Josephus Problem
def __init__(self):

def insert(self, value):
node = Node(value, self.head) #create a node
if self.head == None: #if list is empty insert a node at the start
else:
#iterate through the list till last node is found, i.e., last node next pointer refers to the first node.
temp = temp.next

temp.next = node #adding a new node

else:
#get the last node
temp = temp.next
temp.next = self.head #make the last next refer to the new head
del deleted_node

#remove the node with the given value from the list or throw an error
def delete(self, value):
if self.head: #if the list is not empty
if self.head.value == value: #if the node to be deleted is the first node
return
else:
#iterate through the list
if temp.value == value:
prev.next = temp.next
del temp
return
else:
prev = temp
temp = temp.next

raise KeyError(f'Item with the value {value} does not exist')

#traverse the complete list and print the node value
def traverse(self):
if self.head: #list is not empty
#iterate through the list
print(temp.value, end="\t")
temp = temp.next
print("")

#check if the linked list only contains a single node
def isLastNode(self):
return True
else:
return False

#get the kth node beginning from the start node
def getKthNode(start, k):
temp = start
for i in range(1, k):
temp = temp.next
return temp

#initialize linked list with the position of the person/ index as the node's value
for i in range(0, n):
ll.insert(i)
return ll

#main method to solve the Josephus problem
def josephusProblem(n, k):
return None
while not ll.isLastNode():
k_node = getKthNode(start, k)
start = k_node.next
ll.delete(k_node.value)
return start.value

n = 8
k = 3
last_person_index = josephusProblem(n, k)
print("The position of the last person remaining is", last_person_index)
```

Output

The position of the last person remaining is 6

Back to: Data Structure > Data Structure - Linked List