Make middle node the head in a linked list

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>
 
/* 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 5

[forminator_quiz id="3597"]

Space Complexity: O(1), as only temporary variable are being created.

So, in this article, we have tried to explain the most efficient approach to make the middle node head in a linked list. The question uses the two-pointer method which makes it an important one for coding interviews. 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.

Leave a Reply

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