PPractick

The problem

A queue of support tickets is balanced by removing the middle ticket, defined as position ⌊n/2⌋ counting from 0, so for 4 tickets it's the third one and for 7 it's the fourth. Counting first and walking again takes two passes. With fast and slow pointers, you can land slow on the node just before the middle in a single pass by giving fast a two-node head start, and then unlink the middle with one pointer change.

Example: 1 -> 3 -> 4 -> 7 -> 1 -> 2 -> 6 → 1 -> 3 -> 4 -> 1 -> 2 -> 6 (the 7 at index 3 is removed).

Function signature

Node* deleteMiddle(Node* head);  // removes the node at index floor(n / 2); returns the new head

Test cases

Input list	Output list	Explanation
1 -> 3 -> 4 -> 7 -> 1 -> 2 -> 6	1 -> 3 -> 4 -> 1 -> 2 -> 6	n = 7, remove index 3
1 -> 2 -> 3 -> 4	1 -> 2 -> 4	n = 4, remove index 2
2 -> 1	2	n = 2, remove index 1
1	(empty)	n = 1, remove index 0

(Confirm: the middle is index ⌊n/2⌋ (0-based), i.e. the second middle for even lengths (LeetCode 2095); the removed node is freed.)

How interviewers phrase it

• "Delete the middle node of a linked list" (LeetCode 2095).
• Builds on "middle of a linked list" (S.No 158), with the twist that you need the node before the middle.

Clarifying questions to ask

1. Which middle for an even length?
2. What happens for a single node? (The list becomes empty.)
3. Free the deleted node?

Follow-ups to expect

1. "Why start fast two nodes ahead?"
2. "Why can't you just find the middle and delete it?"
3. "How would a prev pointer work?"
4. "Complexity?"

Related questions

• Detect a loop in LL Medium
• Find the starting point in LL Medium
• Length of loop in LL Medium
• Check if LL is palindrome or not Medium
• Remove Nth node from the back of the LL Medium
• Find the intersection point of Y LL Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in