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

C++ Code


#include 
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<


						 

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);
    
    }
}

Output
Linked list before: 1 2 6 4 5
Linked list after : 6 1 2 4 5

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.

Previous post Reverse a stack without using extra space in O(n)
Next post Insert a node after the n-th node from the end

Leave a Reply

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