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.

[adinserter block=”2″] 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
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