Introduction
As we already know how the linked list works, let’s just look at how we can approach deleting the middle of a linked list. In this problem, we are given a linked list, and we have to delete the middle element of the linked list.
Problem Statement Understanding on how to delete the middle element of the linked list.
Letâ€™s understand the problem statement with the help of an example.
Letâ€™s say the given linked list is:
Now we have to delete the middle element of the linked list such that the resultant linked list after deletion will look like this:
Explanation: 3^{rd} node from the linked list has been removed, as it was the middle node of the linked list.
So letâ€™s first think in terms of linked list, what deleting a node means.
Taking the above linked list, 5â†’10â†’15â†’20â†’25 as an example.
So here if we delete the node(10) we get:
So by deleting the node(10) we are making the connection between node(5) and node(15).
Observations for deletion
 If we take some more examples, we will notice that we need the access of the previous and the next node of the node that we wish to delete.
Say, if the deleted node is the target, and its previous node is prev and its next node is next1. So, to do the deletion of the target node from the linked list, we need to do the following operations:
 prevâ†’next = next1
 And finally free the target node
Similarly, in this problem we need to first find the position of the middle node and node previous to the middle node and then following the abovementioned steps of deletion we have to delete the middle element.
So now we will see how to get the middle node and which node will be the middle node of linked list in case of even length and odd length linked list.
Observations for the position of the middle element
Even Length Linked List:
 If there are an even number of nodes in the linked list, there will be two middle nodes, and the second middle node is the one which will get deleted if we want to delete the middle node of the linked list.
 For example, if the given linked list is 5â†’10â†’15â†’20â†’25â†’30, then 15 and 20 will be the two middle nodes of the linked list, and we will remove the second middle node which is 20.
 So our final modified linked list after deletion will be 5â†’10â†’15â†’25â†’30.
Odd Length Linked List:
 If there are an odd number of nodes in the linked list, there will be a single middle node, and we will delete that node from the linked list.
 For example, if the given linked list is 5â†’10â†’15â†’20â†’25, then 15 will be the middle node of the linked list, and we will remove this node from the linked list.
 So our final modified linked list after deletion will be 5â†’10â†’20â†’30.
Note: If there is just one node present in the input linked list, that node should be removed and a new head should be returned.
Approach 1 on how to delete the middle element in the linked linked list.
The concept is to count the number of nodes N in a linked list first, then delete the (N/2)^{th} node using the simple deletion method.
The (N/2)^{th} node which we will delete will be the middle node of the linked list.
Algorithm1 on how to delete the middle element in the linked linked list.
 If head is NULL, return NULL.
 If next of head is NULL, delete head and return NULL.
 Create a node Head_copy and make it point to the head.
 Initialize a counter variable count = 0, and now with help of head, traverse the linked list incrementing the count variable by 1 for each node of the linked list.
 Finally, when the traversal of the list will be over count will contain the count of number of nodes in the linked list.
 The position of the middle node of the linked list will be given by (count/2), store it in a variable mid.
 Now starting from the head of the linked list, traverse until the below condition holds:
while (mid > 1) { head = headâ†’next; }
 At the end of the while loop, you will be at the node previous of the middle node. So now make headâ†’next = headâ†’nextâ†’next to delete the middle node of the linked list.
 Finally, return Head_copy, which is the head of the newly formed list.
Code Implementation on how to delete the middle element in the linked linked list.
#include#include struct Node { int val; struct Node* next; }; // counting the number of nodes present in the list int count_nodes(struct Node* head) { int n_count = 0; while (head != NULL) { head = head>next; n_count++; } return n_count; } // returns head of the newly formed list // after deleting the middle element. struct Node* delete_middle(struct Node* head) { if (head == NULL) return NULL; if (head>next == NULL) { free(head); return NULL; } struct Node* Head_copy = head; // total nodes currently there in the list int count = count_nodes(head); // position of middle element in the list int mid = count / 2; // Delete the middle node while (mid > 1) { head = head>next; } // Delete the middle node head>next = head>next>next; return Head_copy; } // Function to display the list void display_List(struct Node* x) { while (x != NULL) { printf("%d >", x>val); x = x>next; } // Last element points to null printf("NULL\n"); } // function to create a new node. struct Node* newNode(int value) { struct Node* t = (struct Node*)malloc(sizeof(struct Node)); t>val = value; t>next = NULL; return t; } // Driver Function int main() { // Adding elements to the empty list struct Node* head = newNode(5); head>next = newNode(10); head>next>next = newNode(15); head>next>next>next = newNode(20); head>next>next>next>next = newNode(25); printf("Original List\n"); display_List(head); head = delete_middle(head); printf("List after deleting the middle element\n"); display_List(head); return 0; }
// Program to delete middle element of a linked list #includeusing namespace std; // Node in a linked list struct Node { int val; struct Node* next; }; // counting the number of nodes present in the list int count_nodes(struct Node* head) { int n_count = 0; while (head != NULL) { head = head>next; n_count++; } return n_count; } // returns head of the newly formed list // after deleting the middle element. struct Node* delete_middle(struct Node* head) { if (head == NULL) return NULL; if (head>next == NULL) { delete head; return NULL; } struct Node* Head_copy = head; // total nodes currently there in the list int count = count_nodes(head); // position of middle element in the list int mid = count / 2; // Delete the middle node while (mid > 1) { head = head>next; } // Delete the middle node head>next = head>next>next; return Head_copy; } // Function to display the list void display_List(struct Node* x) { while (x != NULL) { cout << x>val << ">"; x = x>next; } // Last element points to null cout << "NULL\n"; } // function to create a new node. Node* newNode(int value) { struct Node* t = new Node; t>val = value; t>next = NULL; return t; } // Driver Function int main() { // Adding elements to the empty list struct Node* head = newNode(5); head>next = newNode(10); head>next>next = newNode(15); head>next>next>next = newNode(20); head>next>next>next>next = newNode(25); cout << "Original List" << endl; display_List(head); head = delete_middle(head); cout << "List after deleting the middle element" << endl; display_List(head); return 0; }
class DeleteMiddle { /* Link list Node */ static class Node { int data; Node next; } // Utility function to create a new node. static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.next = null; return temp; } // count of nodes static int countOfNodes(Node head) { int count = 0; while (head != null) { head = head.next; count++; } return count; } static Node deleteMid(Node head) { if (head == null) return null; if (head.next == null) { return null; } Node copyHead = head; int count = countOfNodes(head); // Find the middle node int mid = count / 2; // Delete the middle node while (mid > 1) { head = head.next; } // Delete the middle node head.next = head.next.next; return copyHead; } // A utility function to print a given linked list static void printList(Node ptr) { while (ptr != null) { System.out.print(ptr.data + ">"); ptr = ptr.next; } System.out.println("NULL"); } /* Driver code*/ public static void main(String[] args) { /* Start with the empty list */ Node head = newNode(5); head.next = newNode(10); head.next.next = newNode(15); head.next.next.next = newNode(20); head.next.next.next.next = newNode(25); System.out.println("Given Linked List"); printList(head); head = deleteMid(head); System.out.println( "Linked List after deletion of middle"); printList(head); } }
# Node in a linked list class Node: def __init__(self): self.data = 0 self.next = None # counting the number of nodes present in the list def countOfNodes(head): count = 0 while (head != None): head = head.next count += 1 return count # returns head of the newly formed list # after deleting the middle element. def deleteMid(head): if (head == None): return None if (head.next == None): del head return None copyHead = head # after deleting the middle element. count = countOfNodes(head) # Find the middle node mid = count // 2 # Delete the middle node while (mid > 1): mid = 1 head = head.next # Delete the middle node head.next = head.next.next return copyHead # Function to display the list def printList(ptr): while (ptr != None): print(ptr.data, end = '>') ptr = ptr.next print('NULL') # function to create a new node. def newNode(data): temp = Node() temp.data = data temp.next = None return temp # Driver Code if __name__=='__main__': # Start with the empty list head = newNode(5) head.next = newNode(10) head.next.next = newNode(15) head.next.next.next = newNode(20) head.next.next.next.next = newNode(25) print("Given Linked List") printList(head) head = deleteMid(head) print("Linked List after deletion of middle") printList(head)
Output
Original List
5â†’10â†’15â†’20â†’25â†’NULL
List after deleting the middle element
5â†’10â†’20â†’25â†’NULL
Time Complexity: O(n), only a single traversal of the linked list is required.
Space Complexity: O(1), No extra space is needed.
In the above Approach 1, we are traversing the linked list twice:
 First traversal to find the length of the linked list
 Then, in the second traversal, moving up to (length/2)^{th} node of the linked list and deleting it.
The first question which we should ask ourselves is that do we actually need to find the length of the linked list to delete the middle node of the linked list?
The answer is No, we donâ€™t need to find the length of the linked list to delete the middle node of the linked list.
Approach 2 on how to delete the middle element in the linked linked list.
Now in this approach we will try to find the middle of the linked list in one traversal. We will see how can we tackle this:
 What if we start by taking two pointers, say slow and fast, and make both of them point to head initially.
 Now what will happen if we make slow jump one place and fast jump two place (fast moving with twice as speed as slow).
 If we notice carefully by doing the above steps, we will see that when the fast will reach the end of the list, the slow will be pointing to the middle of the list.
 With help of this technique, we can reach the middle of the linked list in one single pass, and hence our objective of reaching the middle of the linked list and deleting it will be achieved in one single traversal of the list.
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 middle of the linked list.
So in this way, using slow and fast pointers, we can find the position of the middle element of the linked list and then using its previous node we can delete the middle node of the linked list.
Algorithm 2 on how to delete the middle element in the linked linked list.
 Create two pointers, slow and fast.
 We will also create a temporary pointer prev which will keep track of the previous node of the slow pointer.
 Initially, both slow and fast will be pointing to the head of the linked list.
 Now make slow pointer jump one place and fast pointer jump two places, until fast pointer reaches the end of the list.
 When the fast pointer reaches the end, the slow pointer will be pointing to the middle of the linked list.
 Now using the prev pointer which is keeping track of previous node to the node pointed by slow pointer, remove the node pointed by slow from the linked list by performing the below operations:
1) prevâ†’next = slow>next
2) delete(slow)
 Finally, the middle node has been deleted from the linked list.
Dry Run on how to delete the middle element in the linked linked list.
Code Implementation on how to delete the middle element in the linked linked list.
#include#include struct Node { int val; struct Node* next; }; // counting the number of nodes present in the list int count_nodes(struct Node* head) { int n_count = 0; while (head != NULL) { head = head>next; n_count++; } return n_count; } // returns head of the newly formed list // after deleting the middle element. struct Node* delete_middle(struct Node* head) { if (head == NULL) return NULL; if (head>next == NULL) { free(head); return NULL; } struct Node* Head_copy = head; // total nodes currently there in the list int count = count_nodes(head); // position of middle element in the list int mid = count / 2; // Delete the middle node while (mid > 1) { head = head>next; } // Delete the middle node head>next = head>next>next; return Head_copy; } // Function to display the list void display_List(struct Node* x) { while (x != NULL) { printf("%d >", x>val); x = x>next; } // Last element points to null printf("NULL\n"); } // function to create a new node. struct Node* newNode(int value) { struct Node* t = (struct Node*)malloc(sizeof(struct Node)); t>val = value; t>next = NULL; return t; } // Driver Function int main() { // Adding elements to the empty list struct Node* head = newNode(5); head>next = newNode(10); head>next>next = newNode(15); head>next>next>next = newNode(20); head>next>next>next>next = newNode(25); printf("Original List\n"); display_List(head); head = delete_middle(head); printf("List after deleting the middle element\n"); display_List(head); return 0; }
// Program to delete middle element of a linked list #includeusing namespace std; // Node in a linked list struct Node { int val; struct Node* next; }; // returns head of the newly formed list // after deleting the middle element. struct Node* delete_middle(struct Node* head) { if (head == NULL) return NULL; if (head>next == NULL) { delete head; return NULL; } // Inorder to reach the middle element, // Initializing slow and fast pointers struct Node* slow = head; struct Node* fast = head; // Finding out the middle as well as // previous of middle. // Store previous of slow struct Node* prev; while (fast != NULL && fast>next != NULL) { fast = fast>next>next; prev = slow; slow = slow>next; } // Now, delete the middle element prev>next = slow>next; delete slow; return head; } // Function to display the list void display_List(struct Node* x) { while (x != NULL) { cout << x>val << ">"; x = x>next; } // Last element points to null cout << "NULL\n"; } // function to create a new node. Node* newNode(int value) { struct Node* t = new Node; t>val = value; t>next = NULL; return t; } // Driver Function int main() { // Adding elements to the empty list struct Node* head = newNode(5); head>next = newNode(10); head>next>next = newNode(15); head>next>next>next = newNode(20); head>next>next>next>next = newNode(25); cout << "Original List" << endl; display_List(head); head = delete_middle(head); cout << "List after deleting the middle element" << endl; display_List(head); return 0; }
class DeleteMiddle { /* Link list Node */ static class Node { int data; Node next; } // Deletes middle node and returns head of the modified list static Node deleteMid(Node head) { // Base cases if (head == null) return null; if (head.next == null) { return null; } // Initialize slow and fast pointers to reach middle of linked list Node slow_ptr = head; Node fast_ptr = head; // Find the middle and previous of middle. Node prev = null; // To store previous of slow_ptr while (fast_ptr != null && fast_ptr.next != null) { fast_ptr = fast_ptr.next.next; prev = slow_ptr; slow_ptr = slow_ptr.next; } // Delete the middle node prev.next = slow_ptr.next; return head; } // A utility function to print a given linked list static void printList(Node ptr) { while (ptr != null) { System.out.print(ptr.data + ">"); ptr = ptr.next; } System.out.println("NULL"); } // Utility function to create a new node. static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.next = null; return temp; } /* Driver code*/ public static void main(String[] args) { /* Start with the empty list */ Node head = newNode(1); head.next = newNode(2); head.next.next = newNode(3); head.next.next.next = newNode(4); System.out.println("Given Linked List"); printList(head); head = deleteMid(head); System.out.println("Linked List after deletion of middle"); printList(head); } }
# Node in a linked list class Node: def __init__(self, data): self.data = data self.next = None # Create and handle list operations class LinkedList: def __init__(self): # Head of the list self.head = None # Add new node to the list end def addToList(self, data): newNode = Node(data) if self.head is None: self.head = newNode return last = self.head while last.next: last = last.next last.next = newNode # Returns the list in string format def __str__(self): linkedListStr = "" temp = self.head while temp: linkedListStr += str(temp.data) + ">" temp = temp.next return linkedListStr + "NULL" # Method deletes middle node def deleteMid(self): # Base cases if (self.head is None or self.head.next is None): return # Initialize slow and fast pointers # to reach middle of linked list slow_Ptr = self.head fast_Ptr = self.head # Find the middle and previous of middle prev = None # To store previous of slow pointer while (fast_Ptr is not None and fast_Ptr.next is not None): fast_Ptr = fast_Ptr.next.next prev = slow_Ptr slow_Ptr = slow_Ptr.next # Delete the middle node prev.next = slow_Ptr.next # Driver code linkedList = LinkedList() linkedList.addToList(5) linkedList.addToList(10) linkedList.addToList(15) linkedList.addToList(20) linkedList.addToList(25) print("Original List") print(linkedList) linkedList.deleteMid() print("List after deleting the middle element") print(linkedList)
Output
Original List
5â†’10â†’15â†’20â†’25â†’NULL
List after deleting the middle element
5â†’10â†’20â†’25â†’NULL
Time Complexity: O(n), only a single traversal of the linked list is required.
Conclusion for deleting the middle element in the linked list.
In this article, we have tried to explain the algorithm for deleting the middle element in the linked list. This problem is interesting as well as important from the interviewâ€™s point of view. 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.
FAQs

What is the time complexity for deleting the middle element in the linked list.?
The time complexity for deleting the middle element in the linked list is O(n). 
What is lazy deletion?
It’s an alternative method to the standard deletion method. Generally, we delete elements logically, but here we delete the elements physically by marking them as deleted by using boolean value. 
What’s the main drawback of a singly linked list?
As we are aware of the structure of linked list, the memory which is used is required more as a pointer stores the address of the next element.