When you start learning about data structures, the linked list often feels confusing. You can’t simply jump to an index, unlike arrays. If someone asks you to find the middle of linked list elements or, more specifically, to delete middle of the linked list nodes, you might initially feel stuck. Let’s look at how to do this.
Also Read – Geometric Algorithms
What is a Middle Node in Linked List?
Before we learn about the code, we need to define what the “middle” actually is. In a linked list, the middle depends on whether the total number of nodes is odd or even.
- Odd Number of Nodes: If there are five nodes, the third node is in the middle.
- Even Number of Nodes: If there are 4 nodes, standard competitive programming problems typically consider the 2nd middle one (the 3rd node) as the target for deletion.
The primary challenge lies in the fact that a linked list only allows forward movement. You can only move forward. This makes the middle of the linked list difficult to find.
The Two-Pointer Approach In Middle of Linked List
The most useful way to solve this is the “Fast and Slow Pointer” method. Instead of counting all nodes and then traversing again, we use two pointers starting at the head.
- Slow Pointer: Moves one step at a time.
- Fast Pointer: Moves two steps at a time.
By the time the fast pointer reaches the end of the list, the slow pointer will be sitting exactly at the middle of the linked list.
Why Use This Method?
- Time Complexity: O(N) – You only traverse the list once.
- Space Complexity: O(1) – You don’t need extra arrays or memory.
Also Read – Introduction to Red-Black Tree
How to Delete Middle of Linked List?
To delete middle of linked list nodes, finding the middle is only half the battle. You actually need to stop one step before reaching the middle. Why? To remove a node, you must change the next pointer to the node preceding it.
Step-by-Step Logic:
- Check for Edge Cases: If the list is empty or has only one node, there is nothing to delete or the list becomes empty.
- Initialise Pointers: Set slow and fast for the head. Keep a previous pointer to track the node before slowing.
- Traverse: Move fast by two and slow by one. Update prev to the current slow before slow moves forward.
- Re-link: Once fast reaches the end, slow is at the middle. Set prev.next = slow.next.
- Memory Cleanup: In languages like C++, you should free the memory of the slow node.
Examples of Deleting the Middle Node in a Linked List
Example 1: Odd number of nodes
Input: 1 → 2 → 3 → 4 → 5
Middle node: 3
Output after deletion: 1 → 2 → 4 → 5
In a linked list with five nodes, the third node is exactly in the middle. After finding it, we remove it by connecting node 2directly to node 4.
Example 2: Even number of nodes
Input: 2 → 4 → 6 → 7 → 5 → 1
Middle node to delete: 7
Output after deletion: 2 → 4 → 6 → 5 → 1
When the list has an even number of nodes, the second middle node is usually deleted. Here, 7 is removed.
Example 3: Single-node linked list
Input: 9
Middle node: 9
Output after deletion: NULL
If the linked list has only one node, deleting the middle makes the list empty.
Example 4: Two-node linked list
Input: 10 → 20
Middle node to delete: 20
Output after deletion: 10
In a two-node linked list, the second node is generally treated as the middle node for deletion.
Middle Element in Linked List in C
If you are working in a low-level language, memory management is your responsibility. When you want to find middle element in linked list in c, your structure usually looks like this:
The Code Logic:
- Create a struct for the node.
- Use the while(fast != NULL && fast->next != NULL) condition.
- Once the loop finishes, the slow pointer holds the address of the middle.
In C, the deletion requires you to manually handle the pointer redirection. If you skip the step, you end up with a memory leak. Always ensure that the node being bypassed is properly handled.
Middle of Linked List Java Solutions
Java handles memory through garbage collection, which makes the middle of the linked list implementation in Java slightly more straightforward. You don’t need to “free” the node; just make sure no other code references it.
Java Implementation Insight:
- Use a simple ListNode class.
- Assign slow = head and fast = head.
- Iterate through the list using a while loop.
- After the loop, the slow pointer represents the middle of the linked list.
If your task is to delete middle of the linked list, you would maintain a temp node that stays one position behind the slow pointer. By setting temp.next = temp.next.next, you effectively drop the middle node from the chain.
Common Mistakes to Avoid in Linked List
While the logic seems simple, many students trip up on a few specific areas:
- Null Pointer Exceptions: Always check if fast.next is null before trying to access fast.next.next.
- Single Node Lists: If the list has only one node, your “prev” pointer might remain null. Ensure you handle this by returning null or an empty list.
- The Even Number Rule: Make sure you know if your specific problem wants you to delete the first middle or the second middle in an even-sized list.
Also Read – Advance Data Structure and Algorithms
Comparison Between Approaches to Find Middle of Linked List
The two-pointer method is the most effective approach for both locating the middle of the linked list and executing a deletion. It is efficient and respects the constraints of a linked data structure.
| Approach | Time Complexity | Space Complexity | Best For |
| Two-Pass (Counting) | O(N + N/2) | O(1) | Beginners |
| Two-Pointer (Fast/Slow) | O(N) | O(1) | Interviews / Efficiency |
| Array Conversion | O(N) | O(N) | Quick debugging (not recommended) |
FAQs
What happens if the linked list only has two nodes?
In a two-node list, the second node is typically considered the middle of the linked list. The fast pointer will move to the end, and the slow pointer will move to the second node. You would set the first node's next pointer to null to delete it.
Why is the two-pointer approach better than counting nodes?
Counting nodes requires two full passes through the list: once to count and once to reach the middle. The two-pointer approach finds the middle of the linked list in a single pass, making it faster in practice.
How do I handle the task of deleting the middle of a circular linked list?
For circular lists, the termination condition changes. Instead of checking for null, you check if the fast pointer has looped back to the head.
Can I use this logic to find the middle of the linked list in C++?
Yes, the logic for C++ is nearly identical to the find middle element in linked list in C approach. The only difference is the use of classes or structs and the delete keyword for memory management.
Is it possible to delete the middle node without a "prev" pointer?
It is possible by copying the data from the next node into the current (middle) node and then deleting the next node. However, this approach doesn't work if the middle node is the last node in the list. The prev pointer method is safer and more standard for middle-of-the-linked-list problems.