Watch 10 video solutions for Delete the Middle Node of a Linked List, a medium level problem involving Linked List, Two Pointers. This walkthrough by codestorywithMIK has 14,171 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.
The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.
n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.
Example 1:
Input: head = [1,3,4,7,1,2,6] Output: [1,3,4,1,2,6] Explanation: The above figure represents the given linked list. The indices of the nodes are written below. Since n = 7, node 3 with value 7 is the middle node, which is marked in red. We return the new list after removing this node.
Example 2:
Input: head = [1,2,3,4] Output: [1,2,4] Explanation: The above figure represents the given linked list. For n = 4, node 2 with value 3 is the middle node, which is marked in red.
Example 3:
Input: head = [2,1] Output: [2] Explanation: The above figure represents the given linked list. For n = 2, node 1 with value 1 is the middle node, which is marked in red. Node 0 with value 2 is the only node remaining after removing node 1.
Constraints:
[1, 105].1 <= Node.val <= 105Problem Overview: You receive the head of a singly linked list and must delete the middle node, returning the updated list. The middle is defined as the ⌊n / 2⌋ index (0‑based). If the list has only one node, deleting the middle results in an empty list.
This problem tests your ability to traverse a linked list efficiently and manipulate node pointers without extra memory. The challenge is identifying the middle node and updating the previous node’s next pointer correctly.
Approach 1: Two-Pass Method (O(n) time, O(1) space)
Traverse the linked list once to compute its length. The middle index is n // 2. Perform a second traversal to reach the node just before the middle. Update its next pointer to skip the middle node (prev.next = prev.next.next). This approach is straightforward because you explicitly know the target index before deletion. The downside is two full passes over the list, but the complexity still remains linear with constant extra memory.
The main operations are simple pointer iteration and index tracking. If the list length is 1, return null. Otherwise, stop at index (n // 2) - 1 and rewire the pointer. This method is easy to reason about and useful when interviewers want to see a clear baseline solution for linked list traversal.
Approach 2: Two-Pointer Method (O(n) time, O(1) space)
This is the optimal one-pass technique using the classic two pointers pattern. Maintain two pointers: slow and fast. Move fast two steps at a time and slow one step. When fast reaches the end of the list, slow will be at the middle node.
To delete the middle node, you also track the previous node of slow. Each iteration updates prev = slow, then advances the pointers (slow = slow.next, fast = fast.next.next). Once the loop ends, remove the middle by setting prev.next = slow.next. This eliminates the middle node without needing the list length.
The key insight is that the fast pointer moves twice as quickly, so when it finishes the list traversal, the slow pointer has covered exactly half the distance. This technique frequently appears in linked list tasks like cycle detection, finding the middle node, and splitting lists.
Recommended for interviews: Start by explaining the two-pass counting approach to demonstrate basic linked list traversal. Then move to the one-pass two-pointer technique, which most interviewers expect. Both run in O(n) time with O(1) space, but the single-pass solution shows stronger pointer manipulation skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass Method (Count then Delete) | O(n) | O(1) | When you want the simplest logic and explicit middle index |
| Two-Pointer Method (Fast & Slow) | O(n) | O(1) | Preferred interview solution using a single traversal |