Delete the Middle Node of a Linked List

LeetCode 2095: Delete the Middle Node of a Linked List Solution & Explanation

Problem Overview

TL;DR: Use the Two Pointer technique (Fast and Slow) to traverse the list in a single pass, locating the node immediately preceding the middle node to adjust its next pointer.

You are given the head of a linked list and tasked with deleting the middle node. The problem defines the middle node based on the size n of the list: it is the ⌊n / 2⌋-th node (using 0-based indexing). After removing the node, return the head of the modified list.

This is a popular interview question, often referred to as LeetCode 2095, that tests your ability to manipulate pointers efficiently without using extra space or multiple passes.

Brute Force Approach for Delete the Middle Node of a Linked List

The naive approach relies on a two-pass strategy. Since we cannot determine the middle index without knowing the total length of the list, we must first count the nodes.

1. First Pass: Traverse the entire linked list to calculate the total length n.
2. Calculate Index: Determine the index of the node to delete: target = floor(n / 2).
3. Second Pass: Traverse the list again from the head, stopping at the node just before the target index (target - 1).
4. Delete: Update the next pointer of the predecessor node to skip the middle node.

Pseudo-code:

length = 0
current = head
while current is not null:
    length++
    current = current.next

target_index = length / 2
current = head
for i from 0 to target_index - 1:
    current = current.next

current.next = current.next.next
return head

Complexity Analysis:

• Time Complexity: $O(N) + O(N/2) \approx O(N)$. While technically linear, this requires traversing the list twice.
• Space Complexity: $O(1)$.
• Why it is suboptimal: In strict system constraints or very large distributed lists, minimizing passes is crucial for performance. The brute force solution works but demonstrates a lack of familiarity with pointer arithmetic patterns.

Algorithm Strategy: Two Pointer Patterns

1. Edge Case Handling: If the list has only one node (head.next is null), the middle node is the head itself. We return null (or the equivalent empty list).
2. Pointer Initialization:
   • Initialize slow to head.
   • Initialize fast to head.next.next. This "head start" for the fast pointer effectively shifts the final position of the slow pointer backward by one, landing it on the predecessor of the middle node rather than the middle node itself.
3. Traversal:
   • Loop while fast is not null and fast.next is not null.
   • In each iteration, move slow forward by 1 node.
   • Move fast forward by 2 nodes.
4. Deletion:
   • Once the loop terminates, slow points to the node before the middle.
   • Update slow.next to point to slow.next.next, effectively unlinking the middle node.
5. Return: Return the original head.

Execution Flow

Consider the input head = [1, 3, 4, 7, 1, 2, 6]. Length is 7. Middle node is 7 (index 3).

1. Check Edge Case: List size is > 1. Proceed.
2. Init:
   • slow points to 1 (Index 0).
   • fast points to 4 (Index 2).
3. Iteration 1:
   • fast (Index 2) and fast.next (Index 3) are valid.
   • slow moves to 3 (Index 1).
   • fast moves to 1 (Index 4).
4. Iteration 2:
   • fast (Index 4) and fast.next (Index 5) are valid.
   • slow moves to 4 (Index 2).
   • fast moves to 6 (Index 6).
5. Iteration 3:
   • fast is at Index 6. fast.next is null. Loop terminates.
6. Deletion:
   • slow is at node 4 (Index 2). The middle node is 7 (Index 3).
   • Execute slow.next = slow.next.next.
   • Node 4 now points to 1 (Index 4), skipping 7.
7. Result: [1, 3, 4, 1, 2, 6].

Proof of Correctness

The correctness relies on the arithmetic series of the pointers. Let $N$ be the number of nodes. The fast pointer moves 2 steps for every 1 step of slow. Normally, slow travels $N/2$ steps when fast travels $N$ steps. By initializing fast at index 2 (conceptually head.next.next), we effectively simulate a race where fast has already traveled 2 units. When fast reaches the end ($N$), slow has traveled $(N - 2) / 2 = N/2 - 1$. Index $N/2 - 1$ is exactly the predecessor of the middle node $N/2$. This logic holds for both odd and even lengths due to integer division behavior.

Pattern Reuse Notes

The Two Pointer pattern used here is fundamental for linked list problems. Similar logic applies to:

• LeetCode 19: Remove Nth Node From End of List - Uses a fixed gap (separation) between pointers to find a relative position from the end.
• LeetCode 876: Middle of the Linked List - Uses the exact same Fast/Slow logic, but returns the middle node instead of deleting it.

Reference Implementation

C++ Solution for LeetCode 2095

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    ListNode* deleteMiddle(ListNode* head) {
14        // Edge case: If list has only 1 node, return nullptr
15        if (head == nullptr || head->next == nullptr) {
16            return nullptr;
17        }
18
19        ListNode* slow = head;
20        // Start fast two steps ahead to ensure slow stops at the predecessor
21        ListNode* fast = head->next->next;
22
23        while (fast != nullptr && fast->next != nullptr) {
24            slow = slow->next;
25            fast = fast->next->next;
26        }
27
28        // Delete the middle node
29        ListNode* toDelete = slow->next;
30        slow->next = slow->next->next;
31        delete toDelete; // Optional: Free memory in C++
32
33        return head;
34    }
35};

Java Solution for LeetCode 2095

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: If list has only 1 node, return null
14        if (head == null || head.next == null) {
15            return null;
16        }
17
18        ListNode slow = head;
19        // Start fast two steps ahead so slow lands on the node BEFORE middle
20        ListNode fast = head.next.next;
21
22        while (fast != null && fast.next != null) {
23            slow = slow.next;
24            fast = fast.next.next;
25        }
26
27        // Skip the middle node
28        slow.next = slow.next.next;
29
30        return head;
31    }
32}

Python Solution for LeetCode 2095

1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, val=0, next=None):
4#         self.val = val
5#         self.next = next
6class Solution:
7    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
8        # Edge case: If list has only 1 node, return None
9        if not head or not head.next:
10            return None
11        
12        slow = head
13        # Start fast two steps ahead
14        fast = head.next.next
15        
16        while fast and fast.next:
17            slow = slow.next
18            fast = fast.next.next
19            
20        # slow is now at the predecessor of the middle node
21        slow.next = slow.next.next
22        
23        return head