Insert a node into the middle of the linked list

In this article, we will learn the algorithm to insert a node at the middle of linked list. Insertion is one of the important concepts in the linked list as we have to deal with links and have to change links accordingly. Let’s try to think the logic for algorithm to insert an element in the middle of a linked list.

How to insert an element in the middle of a linked list

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.

Let’s learn to program online and try to understand the algorithm to insert a node at the middle of linked list 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 will look like:

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 in the middle of the linked list so the node with value x = 6 will be inserted just after the node with the 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 the algorithm to insert an element in the middle of a linked list. 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 for the algorithm to insert an element in the middle of a linked list. 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 for the algorithm to insert a node at the middle of linked list (Using the length)

In this approach:

  • We will first find the length of the linked list i.e., the 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 to insert a node at the middle of linked list

  • 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 the algorithm to insert an element in the middle of a linked list, 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 points 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 to to insert a node at the middle of linked list(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 to insert a node at the middle of linked list

  • 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 of the algorithm to insert a node at the middle of linked list

## Code Implementation of the algorithm to insert a node at the middle of linked list

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

struct Node {
    int data;
    struct Node* next;
};
 
// function to create and return a node
struct Node* getNode(int data)
{
    // allocating space
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
 
    // inserting the required data
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
 
// function to insert node at the middle
// of the linked list
void insertAtMid(struct Node** head_ref, int x)
{
    // if list is empty
    if (*head_ref == NULL)
        *head_ref = getNode(x);
    else {
 
        // get a new node
        struct Node* newNode = getNode(x);
 
        struct Node* ptr = *head_ref;
        int len = 0;
 
        // calculate length of the linked list
        //, i.e, the number of nodes
        while (ptr != NULL) {
            len++;
            ptr = ptr->next;
        }
 
        // 'count' the number of nodes after which
        //  the new node is to be inserted
        int count = ((len % 2) == 0) ? (len / 2) :
                                    (len + 1) / 2;
        ptr = *head_ref;
 
        // 'ptr' points to the node after which
        // the new node is to be inserted
        while (count-- > 1)
            ptr = ptr->next;
 
        // insert the 'newNode' and adjust the
        // required links
        newNode->next = ptr->next;
        ptr->next = newNode;
    }
}
 
// function to display the linked list
void display(struct Node* head)
{
    while (head != NULL) {
        printf("%d ",head->data);
        head = head->next;
    }
}
 
// Driver program to test above
int main()
{
    // Creating the list 1->2->4->5
    struct Node* head = NULL;
    head = getNode(1);
    head->next = getNode(2);
    head->next->next = getNode(4);
    head->next->next->next = getNode(5);
 
    printf("Linked list before insertion: ");
    display(head);
 
    int x = 3;
    insertAtMid(&head, x);
 
    printf("\nLinked list after insertion: ");
    display(head);
 
    return 0;
}
#include <bits stdc++.h="">

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();
    }
}
class Node:

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

def insertAtMid(head, x):

    if(head == None):
        head = Node(x)
    else:
        
        newNode = Node(x)

        ptr = head
        length = 0
        
        while(ptr != None):
            ptr = ptr.next
            length += 1

        if(length % 2 == 0):
            count = length / 2
        else:
            count = (length + 1) / 2

        ptr = head

        while(count > 1):
            count -= 1
            ptr = ptr.next

        newNode.next = ptr.next
        ptr.next = newNode

def display(head):
    temp = head
    while(temp != None):
        print(str(temp.data), end = " ")
        temp = temp.next


head = Node(1)
head.next = Node(5)
head.next.next = Node(2)
head.next.next.next = Node(7)
head.next.next.next.next = Node(10)

print("Linked list before insertion: ", end = "")
display(head)

x = 4
insertAtMid(head, x)

print("\nLinked list after insertion: " , end = "")
display(head)

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 explained the algorithm to insert an element in the middle of a linked list. We have explained different approaches to inserting an element in the middle of a linked list either you do it by using length or by the tortoise method. We have explained the full approach with a complete picturised dry run and code implementation in different languages. If you want to solve more questions on Linked List you can follow this link Linked List, which is curated by our expert mentors at PrepBytes,.

## FAQs related to an algorithm to insert an element in the middle of a linked list

**1. Can you insert a node in the middle of the linked list?**
You can add elements to either the beginning, middle or end of the linked list.

**2. What “->” in ptr = ptr->next?**
The -> operator deferences a pointer and retrieves from it the memory index beyond that point indicated by the following name.

**3. What is traversing in the linked list?**
Traversing means visiting each node of the list once in order to perform some operation on the node.

Leave a Reply

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