Josephus Circle Using Circular Linked List


Josephus problem linked list is also known as josephus problem using circular linked list. This problem is continuously asked in the recent interviews. Let us understand the josephus problem linked list.

As we have seen Different types of linked lists, We are aware of Circular linked lists.In this article we are seeing an approach to josephus problem linked list.

How to Solve Josephus Problem Using Circular Linked List

In josephus problem using circular linked list N people are standing in a circle waiting to get executed. The counting begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped, and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed peoples are removed), until only the last person remains, who is given freedom.

Given the total number of person N and a number M, which indicates that M-1 persons are skipped and the Mth person is killed in the circle, your task is to choose the place in the initial circle so that you are the last one remaining (survive).

Understanding of Josephus Problem with Example

Let us understand the problem with the help of an example:

Let’s take an input, where N = 5 and M = 3.

At this point, we have understood the problem statement of josephus problem linked list. Now we will try to formulate an approach for this problem.

Before moving to the approach of josephus problem using circular linked list, try to think about how you can approach this problem.

  • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach of Josephus Problem Using Circular Linked List

  • We will create a circular linked list of size N, and each node will contain its position number in the list as its data.
  • Then, we will traverse the list and, every time delete the Mth node till we are left with only one node.
  • The left node at last is our solution to the problem.

Algorithm of Josephus Problem using Circular Linked List

  1. Create a new node and store its address in the head and also initialize a prev variable with the head.
  2. Run a loop and create a linked list of size N, attaching the nodes created in each iteration to the end of prev and then update the prev.
  3. After the loop is executed, connect the last node with the head of the list, i.e., prev->next = head.
  4. Initialize two pointers ptr1 and ptr2 with head.
  5. Run a while loop till the next node of ptr1 is ptr1 itself and inside the loop,

    • Initialize variable count with 1.
    • Run a while loop till the count is not equal to M.
    • Inside the loop, copy ptr2 in ptr1, move ptr1 forward by one node and increase count by one.
    • After the inner loop ends, remove the Mth node, i.e., ptr2->next = ptr1->next.
    • Update ptr1 with ptr2->next.
  6. After the loop ends, print the data of the last node left, i.e., data of ptr1.

Dry Run of josephus problem linked list.

Code Implementation of josephus Problem using Circular Linked List

Output of josephus problem using circular linked list

Last person left is 4

Time Complexity of josephus problem linked list: O(M*N), where M and N are the inputs.

Conclusion of josephus problem using circular linked list

So in the above article, we have tried to explain how you can solve the josephus problem using circular linked list most optimally. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Singly linked list vs doubly linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Bubble sort linked list
Deletion in doubly linked list Delete the middle node of a linked list
Polynomial addition using linked list Find max value and min value in linked list
Insert a node at a specific position in a linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Delete a node from linked list at a given position
Remove duplicates from unsorted linked list Reverse a linked list in Python

FAQs

  1. What is a circular linked list?
    A circular linked list is a linked list which is connected by the ends to form a circle-like structure.

  2. What is the time complexity of a circular Linked list?
    Operations such as Insertion which do not require traversal has a time complexity of O(1) and if the traversal is required then the time complexity is O(n).

  3. How many null pointers exist in the circular linked list?
    A circular Linked list is a doubly linked list which not only points to the next node but also points to the previous node as well. That’s why a circular linked list contains two null pointers.

  4. How to implement the circular singly linked list?
    To implement a circular singly linked list, we take an external pointer which points to the last node and the last next will be the first node.

Leave a Reply

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