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

### Problem Statement

In this question, we are given a singly linked list. We have to find the middle of the linked list and set it as the head of the linked list.

### Problem Statement Understanding

Suppose the linked list is 1 - > 2 - > 6 - > 4 -> 5. Here, the middle is 6. Now, we will have to remove this from the middle, and make it the head of the list. So, the final Linked list will be 6 - > 1 - > 2 - > 4 - > 5

Input: 1 2 6 4 5

Output: 6 1 2 4 5

Explanation: As the middle node is 6, it becomes the head of the linked list. As we know, to find the middle of a linked list, the best method is the two-pointer method. We will make use of the slow and fast pointer. As soon as we will find the middle node using the slow and fast pointer, we will change the necessary links and make it as the head of the list. Let us have a glance at the approach.

### Approach

Firstly, we have to find the middle of the linked list. For that, we can use the two-pointer method. Initially, both the pointers will point to the head of the linked list. Then, we will move both of the pointers. The fast pointer will jump two places, whereas the slow pointer will one place. When the fast pointer will reach the end of the linked list, the slow pointer will be pointing to the middle of the linked list. We also have to keep the track of the previous node of the middle.

### Algorithm

• Create two pointers- slow and fast. Initially, both the pointers will pointer to the head of the linked list.
• Now, we will keep storing the slow pointer in prev, and make the slow pointer jump one place and the fast pointer jump two places.
• When the fast pointer will reach the end of the linked list, the slow pointer will be pointing to the middle of the linked list.
• Now, we have the slow pointer pointing to the middle of the linked list, and the prev is pointing to the previous node of the middle.
• For the final part, make the node prev point to the next of the middle element, and make the middle point to the head. By doing this, we are removing the connection between the middle and its previous node.
• Lastly, make the middle pointer the head.

### Dry Run #### Code Implementation

C++ Code

```
#include
using namespace std;

class Node
{
public:
int data;
Node* next;
};

{
return;

Node* prev = NULL;
while (fast != NULL && fast->next != NULL)
{

prev = slow;

fast = fast->next->next;

slow = slow->next;
}

prev->next = prev->next->next;
}

{

Node* new_node = new Node();

new_node->data = new_data;

}

void printList(Node* ptr)
{
while (ptr != NULL)
{
cout << ptr->data << " ";
ptr = ptr->next;
}
cout<

```
```
public class PrepBytes
{

static class Node {
int data;
Node next;
Node(int data){
this.data = data;
next = null;
}
}

{
return;

Node prev = null;
while (two_node != null &&
two_node.next != null) {

prev = one_node;

two_node = two_node.next.next;

one_node = one_node.next;
}

prev.next = prev.next.next;
}

static void push(int new_data)
{

Node new_node = new Node(new_data);

}

static void printList(Node ptr)
{
while (ptr != null) {
System.out.print(ptr.data+" ");
ptr = ptr.next;
}
System.out.println();
}

public static void main(String args[])
{
int i;
push(5);
push(4);
push(6);
push(2);
push(1);
System.out.print(" list before: ");

System.out.print(" list After: ");