PPractick

The problem

A music app has a "jump to the middle of the playlist" button. The playlist is a singly linked list whose length isn't stored. Counting the nodes and then walking half-way takes two passes. The tortoise and hare technique does it in one: a slow pointer moves one step at a time and a fast pointer moves two. When the fast pointer runs off the end, the slow one is exactly in the middle. For an even number of nodes, this version returns the second of the two middle nodes.

Example: 1 -> 2 -> 3 -> 4 -> 5 → node 3; 1 -> 2 -> 3 -> 4 -> 5 -> 6 → node 4.

Function signature

Node* middleNode(Node* head);  // second middle for even lengths; head is non-empty

Test cases

Input list	Output (value)	Explanation
1 -> 2 -> 3 -> 4 -> 5	3	Odd length: the exact middle
1 -> 2 -> 3 -> 4 -> 5 -> 6	4	Even length: the second middle
1	1
1 -> 2	2

(Confirm: the list is non-empty; for an even length, return the second middle node (LeetCode 876).)

How interviewers phrase it

• "Return the middle node of a linked list" (LeetCode 876).
• A building block for: palindrome linked list, merge sort on a list, deleting the middle node, reordering a list.

Clarifying questions to ask

1. For an even length, the first or the second middle?
2. Can the list be empty?
3. One pass required?

Follow-ups to expect

1. "Why does the slow pointer end in the middle?"
2. "How do you get the first middle for even lengths?"
3. "What's the two-pass approach?"
4. "Where else is the fast/slow idea used?"
5. "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
• Delete the middle node in LL Medium

All 474 dsa interview questions

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