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.


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 = 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 = node 
      temp = self.head
      #iterate through the list till last node is found, i.e., last node next pointer refers to the first node.
      while != self.head: 
        temp = 
    = node #adding a new node
  def deleteHead(self):
    deleted_node = self.head
    if == self.head: #list contains a single node only
      self.head = None
      #get the last node
      temp = self.head
      while != self.head:
        temp =
      self.head = #update the head = 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
        temp = #node after the head node
        #iterate through the list
        while temp != self.head:
          if temp.value == value:
            del temp
            prev = temp
            temp =
    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 =
      #iterate through the list
      while temp != self.head:
        print(temp.value, end="\t")
        temp =
  #check if the linked list only contains a single node
  def isLastNode(self):
    if == self.head:
      return True
      return False

#get the kth node beginning from the start node
def getKthNode(start, k):
  temp = start
  for i in range(1, k):
    temp =
  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):
  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 = 
  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)


The position of the last person remaining is 6

Back to: Data Structure > Data Structure - Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *