Insert a node into the middle of the linked list

Introduction

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 problem, we are given a singly linked list and a value x. We have to insert a node with the value x into the middle of the list.

Problem Statement Understanding

Let’s learn programming online and try to understand the problem statement with the help of examples.

Suppose the given linked list is:

  • So now, according to the problem statement, we have to insert a node with value x = 4 into the middle of the list such that our resultant [linked list](https://www.prepbytes.com/blog/linked-list/find-the-fractional-or-n-k-th-node-in-linked-list/ "linked list") will look like:
  • ![](https://blog.prepbytes.com/wp-content/uploads/2021/08/output-7.png)

Explanation: Here, the current middle of the list is the node with the value 2, so 4 will be inserted just after 2.

If the given linked list is 1 → 3 → 5 → 7 → 9 → 11 and x = 6.

  • For the above linked list, the node with the value 5 is the middle of the linked list so the node with value x = 6 will be inserted just after the node with value 5 and our resultant linked list will look like: 1 → 3 → 5 → 6 → 7 → 9 → 11

Explanation: Here, the current middle of the list is the node with value 5, so 6 will be inserted just after 5.

I hope from the above examples the problem is clear, and now the main question is how we should approach this problem? What is the first thing that comes to mind?

  • Finding out the length of the list and then adding the new node just after the (length/2)th node if the length is even, else just after the ((length+1)/2)th node if the length is odd.

  • Well, this will be our approach. Then afterward, we will see whether we can optimize it or not.

Let us have a glance at the approaches and see where we can optimize the first approach.

Approach (Using the length)

In this approach:

  • We will first find the length of the linked list i.e., number of nodes in the linked list.
  • As we know if the length is even, then the middle node is (length/2)th node, else the middle is ((length+1)/2)th node.
  • So, if the length is even, we will add the new node after (length/2)th node of the linked list, else we will add the new node after ((length+1)/2)th node of the linked list.

Algorithm

  • With the help of list traversal, find the length of the linked list. Let the length be len.
  • Now, create a variable k. k will (len/2) if len is even, else it will (len+1)/2.
  • Here, k denotes the middle point of the list.
  • Traverse k nodes and add the new node just after the kth node.
  • In this way, the new node gets added into the middle of the list.

This approach is okay, but can we further optimize it?

  • If we think carefully, the answer is yes. We can optimize it, as in this technique, we are doing two traversals of the given list.

What if we start by taking two pointers, say slow and fast, and make both point to the head initially.

  • What will happen if we make the slow jump one place and the fast jump two places.
  • If we notice carefully, by doing the above step, when the fast will reach the end of the list, the slow will be pointing to the middle of the list.
  • With the help of this technique, we can reach the middle node of a linked list in a single pass.

Note: The reason why slow will be pointing to the middle of the linked list when fast reaches the end is that, as our slow pointer is travelling with half of the speed of the fast pointer, so when fast pointer will reach the end of the linked list, till that time slow pointer will have travelled only half the distance as travelled by fast pointer and hence it will be at the middle of the linked list.

Do you know what the above-explained method is called?

  • This method is called the tortoise and hare method or the slow and fast pointer method.

The slow and fast pointer method has been explained in detail in the approach section and the dry run.

Approach (Slow and Fast Pointer)

Let us see what the slow and fast pointer technique is:

  • Initially, both the pointers, slow and fast, will point to the head of the linked list.
  • Then, we will start moving both of the pointers. The fast pointer will jump two places, whereas the slow pointer will jump only one place.
  • When the fast pointer reaches the end of the linked list, the slow pointer will be pointing to the middle of the linked list.
  • Now, as we have the slow pointer pointing to the middle of the list, we will add the new node just after the slow pointer.

Algorithm

  • Create two-pointer slow and fast. Both slow and fast will be pointing to the head of the list.
  • Now, the slow will jump one place and the fast will jump two places.
  • When the fast pointer reaches the end of the list, the slow will be pointing to the middle of the list.
  • Add the new node newNode just after the slow pointer following the below steps.
    • newNode - > next = slow - > next
    • slow - > next = newNode
  • Finally, our newNode will be inserted into the middle of the linked list and our objective will be achieved.

DRY RUN

![](https://blog.prepbytes.com/wp-content/uploads/2021/08/Insert-a-node-into-the-middle-of-the-linked-list-1.png)
![](https://blog.prepbytes.com/wp-content/uploads/2021/08/Insert-a-node-into-the-middle-of-the-linked-list-2.png)

Code Implementation

#include 

using namespace std;

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

Node* getNode(int data)
{

    Node* newNode = (Node*)malloc(sizeof(Node));

    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void insertAtMid(Node** head_ref, int x)
{

    if (*head_ref == NULL)
        *head_ref = getNode(x);

    else {

        Node* newNode = getNode(x);

        Node* slow = *head_ref;
        Node* fast = *head_ref;

        while (fast && fast->next) {

            slow = slow->next;

            fast = fast->next->next;
        }

        newNode->next = slow->next;
        slow->next = newNode;
    }
}

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

int main()
{
    Node* head = NULL;
    head = getNode(1);
    head->next = getNode(5);
    head->next->next = getNode(2);
    head->next->next->next = getNode(7);
    head->next->next->next->next = getNode(10);

    cout << "Linked list before insertion: ";
    display(head);

    int x = 4;
    insertAtMid(&head, x);

    cout << "\nLinked list after insertion: ";
    display(head);

    return 0;
}
import java.util.*;
import java.lang.*;
import java.io.*;

public class LinkedList
{
    static Node head; 

    static class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    static void insertAtMid(int x)
    {

        if (head == null)
        head = new Node(x);

        else {
            Node newNode = new Node(x);

            Node slow = head;
            Node fast = head;

            while (fast != null && fast.next
                                != null)
            {

                slow = slow.next;

                fast = fast.next.next;
            }

            newNode.next = slow.next;
            slow.next = newNode;
        }
    }

    static void display()
    {
        Node temp = head;
        while (temp != null)
        {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }

    public static void main (String[] args)
    {
        head = null;
        head = new Node(1);
        head.next = new Node(5);
        head.next.next = new Node(2);
        head.next.next.next = new Node(7);
        head.next.next.next.next = new Node(10);
        
        System.out.println("Linked list before insertion: ");
        display();

        int x = 4;
        insertAtMid(x);

        System.out.println("\nLinked list after insertion: ");
        display();
    }
}

Output

Linked list before insertion: 1 5 2 7 10
Linked list after insertion: 1 5 2 4 7 10


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

So, in this article, we have tried to explain the most efficient approach to insert a node into the middle of the linked list. This is an important question when it comes to 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 Add 1 To Number Represented As Linked List
Next post Find modular node in a linked list

Leave a Reply

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