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.

`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 class CircularLinkedList: def __init__(self): self.head = None #adds a node at the end of the linked list 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 self.head = node self.head.next = node else: temp = self.head #iterate through the list till last node is found, i.e., last node next pointer refers to the first node. while temp.next != self.head: temp = temp.next temp.next = node #adding a new node def deleteHead(self): deleted_node = self.head if self.head.next == self.head: #list contains a single node only self.head = None else: #get the last node temp = self.head while temp.next != self.head: temp = temp.next self.head = self.head.next #update the head 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 self.deleteHead() return else: temp = self.head.next #node after the head node prev=self.head #iterate through the list while temp != self.head: 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 print(self.head.value, end="\t") #display value of head node temp = self.head.next #iterate through the list while temp != self.head: print(temp.value, end="\t") temp = temp.next print("") #check if the linked list only contains a single node def isLastNode(self): if self.head.next == self.head: 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 def initializeLinkedList(n): ll = CircularLinkedList() #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): ll = initializeLinkedList(n) if ll.head is None: return None start = ll.head 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

Blog Hero