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 abovelinked 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 k^{th} 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 aboveexplained 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 twopointer 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.