Delete the Middle Node of a Linked List

Delete the Middle Node of a Linked List

1. What is this problem about?

The Delete the Middle Node of a Linked List interview question asks you to identify and remove the central node of a singly linked list. If the list has $N$ nodes, the middle node is at index $\lfloor N/2 floor$ (0-indexed). This Delete the Middle Node of a Linked List coding problem is a variation of the classic "Find Middle" problem, but with the added requirement of modifying the structure.

2. Why is this asked in interviews?

Tech firms like Apple and Goldman Sachs use this to check for Two-Pointer interview patterns. It assesses whether you can find a specific position in a list without doing two full passes (one to count and one to delete). It's a test of efficient traversal and pointer manipulation.

3. Algorithmic pattern used

This problem uses the Slow and Fast Pointers (Tortoise and Hare) pattern.

• Maintain a fast pointer that moves 2 steps at a time and a slow pointer that moves 1 step.
• To delete the node, you actually need the node before the middle.
• By the time fast reaches the end, slow will be at the middle. Keeping a prev pointer trailing slow allows you to re-link and delete.

4. Example explanation

List: 1 -> 2 -> 3 -> 4 -> 5.

1. slow and fast start at 1. prev = null.
2. fast moves to 3, slow to 2. prev = 1.
3. fast moves to 5, slow to 3. prev = 2.
4. fast.next is null, stop.
5. Middle is 3. Use prev (node 2) to skip 3: 2.next = 4. Result: 1 -> 2 -> 4 -> 5.

5. Common mistakes candidates make

• Off-by-one: Deleting the node after or before the intended middle because of incorrect loop termination.
• Single Node Case: Forgetting to handle lists with only 1 node, where deleting the middle results in an empty list (null).
• Two-pass logic: Counting the whole list first. While $O(N)$, it’s less elegant than the one-pass two-pointer approach.

6. Interview preparation tip

Whenever you need to find a relative position in a linked list (middle, $k^{th}$ from end, cycle start), immediately think of Slow and Fast Pointers. It's the standard optimization for list traversal.