### Introduction

Linked list is one of the most important concepts and data structures to learn while preparing for coding interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

**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 M^{th} 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).

### Problem Statement Understanding

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. Now we will try to formulate an approach for this problem.

Before moving to the approach section, 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

- 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 M
^{th}node till we are left with only one node. - The left node at last is our solution to the problem.

### Algorithm

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.

- Inside the loop, copy
- After the inner loop ends, remove the M
^{th}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

### Code Implementation

#### Output

Last person left is 4

**Time Complexity:** O(M*N), where M and N are the inputs.

[forminator_quiz id="5901"]

So, in this blog, we have tried to explain how you can solve the Josephus Circle problem Using a 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.