Last Updated on November 28, 2022 by Prepbytes
In this blog, we will deep dive and discuss how to make the middle node head of a linked list. Making the middle node as the head node of the linked list will make your data structures strong and also you will get how to manipulate linked lists as per your requirements. Let’s get back to our topic i.e. to make the middle node head of a linked list.
How To Make Middle Node Head Of A Linked List
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.
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 To Make Middle Node Head Of A Linked List
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 To Make Middle Node Head Of A Linked List
- 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 To Make Middle Node Head Of A Linked List
Code Implementation To Make Middle Node Head Of A Linked List
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* Function to get the middle and set at
beginning of the linked list*/
void setMiddleHead(struct Node** head)
{
if (*head == NULL)
return;
// To traverse list nodes one by one
struct Node* one_node = (*head);
// To traverse list nodes by skipping
// one.
struct Node* two_node = (*head);
// 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;
one_node->next = (*head);
(*head) = one_node;
}
// 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 */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = 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
struct Node* head = NULL;
int i;
for (i = 5; i > 0; i--)
push(&head, i);
printf(" list before: ");
printList(head);
setMiddleHead(&head);
printf(" list After: ");
printList(head);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node* next;
};
void setMiddleHead(Node** head)
{
if (*head == NULL)
return;
Node* slow = (*head);
Node* fast = (*head);
Node* prev = NULL;
while (fast != NULL && fast->next != NULL)
{
prev = slow;
fast = fast->next->next;
slow = slow->next;
}
prev->next = prev->next->next;
slow->next = (*head);
(*head) = slow;
}
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(Node* ptr)
{
while (ptr != NULL)
{
cout << ptr->data << " ";
ptr = ptr->next;
}
cout<<endl;
}
int main()
{
Node* head = NULL;
int i;
push(&head,5);
push(&head,4);
push(&head,6);
push(&head,2);
push(&head,1);
cout << " Linked ist before: ";
printList(head);
setMiddleHead(&head);
cout << " Linked list after: ";
printList(head);
return 0;
}
public class PrepBytes
{
static class Node {
int data;
Node next;
Node(int data){
this.data = data;
next = null;
}
}
static Node head;
static void setMiddleHead()
{
if (head == null)
return;
Node one_node = head;
Node two_node = head;
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;
one_node.next = head;
head = one_node;
}
static void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
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[])
{
head = null;
int i;
push(5);
push(4);
push(6);
push(2);
push(1);
System.out.print(" list before: ");
printList(head);
setMiddleHead();
System.out.print(" list After: ");
printList(head);
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
def setMiddleHead(head):
if(head == None):
return None
one_node = head
two_node = head
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
one_node.next = head
head = one_node
return head
def push(head, new_data):
new_node = Node(new_data)
new_node.next = head
head = new_node
return head
def printList(head):
temp = head
while (temp!=None):
print(str(temp.data), end = " ")
temp = temp.next
print("")
head = None
head = push(head, 5)
head = push(head, 4)
head = push(head, 6)
head = push(head, 2)
head = push(head, 1)
print("list before: ", end = "")
printList(head)
head = setMiddleHead(head)
print("list After: ", end = "")
printList(head)
Output
Linked list before: 1 2 6 4 5
Linked list after : 6 1 2 4 5Space Complexity To Make Middle Node Head Of A Linked List: O(1), as only temporary variables are being created.
This blog has discussed the most efficient approach to make middle node head of a linked list. The question uses the two-pointer method which makes it an important one for coding interviews. Having knowledge for manipulating linked list as per your conditions. 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.
FAQ
1. How do you find the center node in a linked list?
- Create a pointer p , pointing to the head.
- Iterate over the linked list until p reaches to the end of the linked list, thereby finding the length of the list.
- Set p to head again. Now, increment p length/2 times. Now, the p is at the middle of the linked list node.
- Return the value at p.
2. What are the two parts of a node?
A node has two parts: the data part and the next part. The data part contains the stored data, and the next part provides the address of the next node. The first node of a linked list is called the head, and the last node is called the tail.