876 - Middle of the Linked List

Difficulty: Easy | Pattern: Two Pointers (Slow/Fast) | Company tags: Amazon, Apple, Microsoft

Problem Statement

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: head = [1,2,3,4,5]
Output: Node 3 (middle of odd-length list)

Example 2:

Input: head = [1,2,3,4,5,6]
Output: Node 4 (second middle of even-length list)

Solution: Slow/Fast Pointers — O(n), O(1)

Key insight: Move slow one step and fast two steps. When fast reaches the end, slow is at the middle.

def middleNode(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Algorithm Flow

Dry Run

[1,2,3,4,5] (odd length)

slow	fast
1	1
2	3
3	5
—	5.next=None, stop

Return node 3 ✓

[1,2,3,4,5,6] (even length)

slow	fast
1	1
2	3
3	5
4	None (6.next=None), stop

Return node 4 ✓ (second middle)

Why Fast.next Check?

fast.next.next would throw if fast.next is None. The condition fast and fast.next prevents this.

Applications

Finding the middle is a building block for:

• Merge Sort on linked list: split at middle, sort each half
• Palindrome check (LC 234): find middle, reverse second half
• Rotate list (LC 61): find the split point

Complexity

• Time: O(n)
• Space: O(1)

Key Terms

Term	Definition
Slow/fast pointers	Two pointers traversing a list at different speeds to find a midpoint, cycle, or offset without extra storage.
Singly linked list	A list where each node only knows the next node, so traversal is one-directional.
O(1) space traversal	A technique that solves list problems using only a fixed number of pointer variables, no arrays or hash maps.
Loop invariant	The property (here: fast travels twice as far as slow) that guarantees slow lands on the middle when fast finishes.

FAQ

1. Can this be solved without extra space? Yes — that's exactly what slow/fast pointers achieve. No array or count of nodes is needed; it's already O(1) space.
2. What if the list is empty? head is None, so slow = fast = None, the while loop condition fails immediately, and None is returned — correct behavior.
3. What if the list has only one node? fast.next is None on the first check, so the loop never executes and slow (the single node) is returned.
4. How would this change if you needed the first middle node for even-length lists instead of the second? Change the loop condition to while fast.next and fast.next.next so fast stops one step earlier, landing slow on the first middle.
5. What's the common follow-up interviewers ask? "Find the middle without knowing the length in advance" (already solved here in one pass), or "detect if the list has a cycle" — both reuse the same slow/fast pointer technique.

Quick Revision

• Pattern: Two Pointers (Slow/Fast), also called the "tortoise and hare" technique.
• slow moves 1 step, fast moves 2 steps per iteration.
• Loop while fast and fast.next are both non-null to avoid a null-pointer dereference on fast.next.next.
• When fast reaches the end, slow sits at the middle.
• For even-length lists, this naturally lands on the second middle node.
• No need to know the list length ahead of time — solved in a single pass.
• Time: O(n); Space: O(1) — only two pointer variables used.
• Reusable building block for merge sort on linked lists, palindrome checks, and cycle detection.

Related Problems

• 234 - Palindrome Linked List — uses slow/fast to find the middle, then reverses the second half.
• 142 - Linked List Cycle II — same slow/fast pointer technique adapted to detect a cycle's entry point.
• 19 - Remove Nth Node From End of List — related two-pointer technique with a fixed gap between pointers.
• Rotate List (LeetCode 61) — also uses list traversal to find a split point, though not covered in this repo.