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

```#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

/* Function to get the middle and set at
{
return;

// To traverse list nodes one by one

// To traverse list nodes by skipping
// one.

// To keep track of previous of middle
struct Node* prev = NULL;
while (two_node != NULL && two_node->next != NULL) {

/* for previous node of middle node */
prev = one_node;

/* move one node each time*/
two_node = two_node->next->next;

/* move two node each time*/
one_node = one_node->next;
}

/* set middle node at head */
prev->next = prev->next->next;
}

// To insert a node at the beginning of linked
// list.
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));

new_node->data = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

// A  function to print a given linked list
void printList(struct Node* ptr)
{
while (ptr != NULL) {
printf("%d ", ptr->data);
ptr = ptr->next;
}
printf("\n");
}

/* Driver function*/
int main()
{
// Create a list of 5 nodes
int i;
for (i = 5; i > 0; i--)

printf(" list before: ");

printf(" list After:  ");

return 0;
}
```
```#include <bits/stdc++.h>
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<<endl;
}

int main()
{
int i;
cout << " Linked ist before: ";
cout << " Linked list after: ";
return 0;
}

```
```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: ");

}
}

```
```class Node:
def __init__(self, data):
self.data = data
self.next = None

return None

prev = None

while(two_node != None and two_node.next != None):

prev = one_node
one_node = one_node.next
two_node = two_node.next.next

prev.next = prev.next.next

new_node = Node(new_data)

while (temp!=None):

print(str(temp.data), end = " ")
temp = temp.next
print("")

print("list before: ", end = "")

print("list After: ", end = "")