Delete the Middle Node of a Linked List

Med

#1907Time: O(N), where N is the number of nodes in the linked list. The first pass to count nodes takes O(N) time, and the second pass to find the predecessor takes up to O(N/2) time. The total complexity is O(N).Space: O(1), as we only use a constant amount of extra space for pointers and a counter, regardless of the list size.

Patterns

Two Pointers

Data structures

Linked List

Prompt

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.

For 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:

The number of nodes in the list is in the range [1, 10⁵].
1 <= Node.val <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward approach is to first determine the size of the linked list by traversing it completely. Once the size n is known, we can calculate the position of the middle node (floor(n / 2)). Then, we perform a second traversal to reach the node just before the middle node and update its next pointer to bypass and thus delete the middle node.

Algorithm

Handle the edge case where the list has zero or one node. If head is null or head.next is null, the middle node is the head itself. Deleting it results in an empty list, so we return null.
First Pass: Traverse the entire linked list to count the total number of nodes, n.
Calculate the index of the middle node, which is middleIndex = n / 2.
To delete the middle node, we need to find its predecessor. The predecessor is at middleIndex - 1.
Second Pass: Initialize a pointer prev to head. Traverse the list middleIndex - 1 times to move prev to the predecessor of the middle node.
Once prev is at the correct position, update its next pointer to skip the middle node: prev.next = prev.next.next.
Return the original head of the list.

Walkthrough

This method breaks the problem down into two simpler sub-problems: finding the list's length and then finding a specific node by its index.

Count Nodes: We start by iterating through the list from the head with a temporary pointer and a counter. The loop continues until the pointer becomes null, giving us the total count n of nodes.
Handle Edge Case: If n is 1, the list becomes empty. The problem constraints state n >= 1, so we handle the n=1 case by returning null.
Find Predecessor: The middle node is at index n / 2. To delete it, we need its predecessor, which is at index n / 2 - 1. We start another traversal from the head and iterate (n / 2) - 1 times. The node we land on is the predecessor of the middle node.
Delete Node: Let the predecessor node be prev. The middle node is prev.next. We perform the deletion by setting prev.next = prev.next.next. This effectively removes the middle node from the list.

For example, in a list [1,3,4,7,1,2,6], n=7. The middle index is 7/2 = 3. The predecessor is at index 3-1=2. We traverse to the node at index 2 (value 4), and set its next to point to the node at index 4 (value 1), skipping the node at index 3 (value 7).

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode deleteMiddle(ListNode head) {13        if (head == null || head.next == null) {14            return null;15        }16 17        // First pass: count the number of nodes18        int n = 0;19        ListNode temp = head;20        while (temp != null) {21            n++;22            temp = temp.next;23        }24 25        // Calculate the index of the node to stop at (the one before the middle)26        int middleIndex = n / 2;27 28        // Second pass: find the node before the middle29        ListNode prev = head;30        // We need to traverse middleIndex - 1 steps from the head31        for (int i = 0; i < middleIndex - 1; i++) {32            prev = prev.next;33        }34 35        // Delete the middle node36        prev.next = prev.next.next;37 38        return head;39    }40}

Complexity

Time

O(N), where N is the number of nodes in the linked list. The first pass to count nodes takes O(N) time, and the second pass to find the predecessor takes up to O(N/2) time. The total complexity is O(N).

Space

O(1), as we only use a constant amount of extra space for pointers and a counter, regardless of the list size.

Trade-offs

Pros

The logic is simple and directly follows from the problem definition.
It's easy to implement and debug.

Cons

Requires traversing the list twice (or one and a half times), which is less efficient than a single-pass solution in terms of the number of operations and potential cache performance.

A more efficient approach is to use the classic fast and slow pointer technique. This allows us to find the middle of the list (or its predecessor) in a single pass, eliminating the need for a preliminary count of the nodes. By carefully initializing the pointers, we can make the slow pointer stop exactly at the node before the one we want to delete.

Algorithm

Handle the edge case: if the list has only one node (head.next == null), return null.
Initialize a slow pointer to head.
Initialize a fast pointer to head.next.next. This specific initialization is key to making slow land on the predecessor of the middle node.
Loop while fast != null and fast.next != null:
- Move slow one step forward: slow = slow.next.
- Move fast two steps forward: fast = fast.next.next.
After the loop terminates, the fast pointer has reached the end of the list, and the slow pointer is positioned at the node just before the middle node.
Delete the middle node by updating the next pointer of the slow node: slow.next = slow.next.next.
Return head.

Walkthrough

This optimized method uses two pointers, slow and fast, to traverse the list simultaneously but at different speeds. The fast pointer moves twice as fast as the slow pointer.

Edge Case: First, we check if the list has only one node (head.next == null). If so, deleting the middle node leaves an empty list, so we return null.
Pointer Initialization: We initialize slow to head and fast to head.next.next. This setup is crucial. When the fast pointer reaches the end, slow will naturally be at the predecessor of the middle node.
Traversal: We iterate through the list with the condition while (fast != null && fast.next != null). In each step, slow moves one node forward, and fast moves two nodes forward.
Finding the Predecessor: Let's trace for a list of size 5 (n=5). The middle is at index 2. We need the predecessor at index 1.
- Initial: slow at index 0, fast at index 2.
- Iter 1: slow moves to index 1, fast moves to index 4.
- Loop ends because fast.next is null. slow is at index 1, which is the correct predecessor.
Deletion: Once the loop finishes, slow points to the node before the middle. We can then delete the middle node (slow.next) by setting slow.next = slow.next.next.

This approach is superior as it combines finding the correct position and performing the deletion into a single, efficient pass.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode deleteMiddle(ListNode head) {13        // Edge case: list with only one node.14        if (head.next == null) {15            return null;16        }17 18        // Initialize slow and fast pointers.19        // slow will point to the node before the middle.20        ListNode slow = head;21        ListNode fast = head.next.next;22 23        // Move fast pointer two steps and slow pointer one step.24        while (fast != null && fast.next != null) {25            slow = slow.next;26            fast = fast.next.next;27        }28 29        // slow is now at the predecessor of the middle node.30        // Delete the middle node.31        slow.next = slow.next.next;32 33        return head;34    }35}

Complexity

Time

O(N), where N is the number of nodes. The list is traversed only once. The `fast` pointer reaches the end in N/2 steps, making the approach linear.

Space

O(1), as we only use a constant amount of extra space for the two pointers.

Trade-offs

Pros

Highly efficient, requiring only a single pass over the linked list.
Uses constant extra space.
It's an elegant solution and a common, useful pattern for solving linked list problems.

Cons

The pointer initialization and movement logic can be slightly less intuitive for beginners compared to the two-pass approach.

Solutions

Solution

1/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode deleteMiddle ( ListNode head ) { ListNode dummy = new ListNode ( 0 , head ); ListNode slow = dummy , fast = head ; while ( fast != null && fast . next != null ) { slow = slow . next ; fast = fast . next . next ; } slow . next = slow . next . next ; return dummy . next ; } }

1/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * deleteMiddle ( ListNode * head ) { ListNode * dummy = new ListNode ( 0 , head ); ListNode * slow = dummy ; ListNode * fast = head ; while ( fast && fast -> next ) { slow = slow -> next ; fast = fast -> next -> next ; } slow -> next = slow -> next -> next ; return dummy -> next ; } };

1# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def deleteMiddle ( self , head : Optional [ ListNode ]) -> Optional [ ListNode ]: dummy = ListNode ( next = head ) slow , fast = dummy , head while fast and fast . next : slow = slow . next fast = fast . next . next slow . next = slow . next . next return dummy . next

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem