middle-of-linked-list

Difficulty: Easy  ·  Topic: Linked List  ·  Practice it on parikshan: /practice/middle-of-linked-list/start

The story

The Linux kernel's CFS (Completely Fair Scheduler) maintains a red-black tree of runnable tasks, but earlier kernels used a doubly-linked run queue. Finding the median-priority task in that queue without a second traversal is a one-pass problem: walk one pointer at half-speed, walk another at full-speed; when the fast pointer falls off the end, the slow pointer is at the midpoint.

That is the slow/fast pointer trick, also called Floyd's tortoise-and-hare. middle-of-linked-list is its purest expression. It is also the precursor to cycle detection (which uses the same skeleton to prove that fast and slow eventually collide inside a cycle) and to palindrome-linked-list (which uses the midpoint to compare the two halves).

What's actually being asked

Given the head of a non-empty singly linked list, print the value of its middle node. If the list has even length, print the value of the second middle node (the one closer to the tail). For example, [1, 2, 3, 4, 5] → 3; [1, 2, 3, 4, 5, 6] → 4.

The naive approach

Walk the list once to count n. Then walk again n // 2 steps to land at the middle. Two passes, O(n) time, O(1) space. Correct and easy.

A third naive: load every value into an array, return arr[n // 2]. O(n) time, O(n) space. Also correct, and acceptable when you also need random access for some downstream step.

Both work. Neither is the answer the problem wants. The problem is here to teach the one-pass trick that powers cycle detection.

The key insight

Two walkers leave the head at the same time. The slow walker takes one step per turn; the fast walker takes two. When the fast walker reaches the end (fast is null or fast.next is null), the slow walker has taken exactly half as many steps and is therefore at the middle.

Two end conditions are required because "the end" can be hit on either step of the fast walker's pair:

• fast is None: fast just took its second sub-step past the last node.
• fast.next is None: fast just landed on the last node.

For odd n (e.g., 5 nodes), fast lands exactly on the last node (positions 0, 2, 4 against length 5). The loop exits with fast.next is None. Slow is at position 2, the middle.

For even n (e.g., 6 nodes), fast overshoots the last node (positions 0, 2, 4, 6 ≡ null against length 6). The loop exits with fast is None. Slow is at position 3, the second middle.

That is the convention this problem demands. If you wanted the first middle for even lengths, you would use a "while fast.next and fast.next.next" loop instead.

Step-by-step approach

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def middle_node(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

Loop invariant in English: slow has taken half as many steps as fast, and both are still inside the list. When the loop exits, fast is past or at the tail; slow is at the midpoint by the parity rule above.

The order of the while conditions matters: fast is not None must come first because Python short-circuits left-to-right. If fast is null, attempting to read fast.next raises an AttributeError. Reversing the order is a common AI-agent bug.

Worked example

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

Return slow.val = 3. ✓

Even: 1 -> 2 -> 3 -> 4 -> 5 -> 6.

Return slow.val = 4. ✓ (Second middle of 6, as required.)

Counter-case: single node [42]. Loop never runs (fast.next is null). Return 42.

Complexity

• Time: O(n). Fast does roughly n / 2 two-step iterations; slow does the same number of one-step iterations. Total work is O(n).
• Space: O(1). Two pointer variables.

The one-pass beats the two-pass by a constant factor, not asymptotically. The deep reason to learn it is the cycle-detection and palindrome applications, where the two-pass version does not exist or is far uglier.

Common pitfalls

1. Conditions in the wrong order: while fast.next is not None and fast is not None will throw on the empty list. The null check on fast must come first.
2. Wrong loop condition for "first middle": using while fast and fast.next and fast.next.next returns the first middle on even lengths, the second middle on odd lengths. Spec mismatch.
3. Mutating during traversal: any code that re-assigns head while walking loses the original head reference. The slow/fast template uses two fresh pointers and leaves head alone.
4. Two-pass code for an interview: technically correct but signals the candidate has not internalised the Linked List toolkit. Always one-pass when one-pass is available.

Where this shows up in the enterprise

• Cycle detection in production: Floyd's tortoise-and-hare is the standard O(1)-space cycle detector used in Go's runtime to detect infinite recursion in goroutine stack walks.
• Median-of-stream calculations: an inline median over a linked-list buffer (Datadog histograms, Splunk percentile aggregators) uses this exact skeleton.
• Music apps' shuffle midpoint: Spotify's "play from the middle of the queue" feature.
• Kernel run-queue median: as in the Linux CFS story above.
• LRU cache eviction midpoint: some adaptive cache policies (ARC, 2Q) split the cache into halves and need the midpoint pointer maintained as the list grows.
• Linked-list merge sort split: the merge-two-sorted-lists editorial mentions this; sort-list needs the midpoint to split the list before recursing.

Variants you'll see elsewhere

• linked-list-cycle: same template; the loop body checks slow == fast to detect a cycle.
• linked-list-cycle-ii: cycle plus return the start of the cycle. Build on cycle detection plus Floyd's second-phase math.
• palindrome-linked-list: use the midpoint to split, reverse the second half, compare.
• reorder-list: midpoint plus second-half reverse plus weave.
• sort-list: merge-sort on a linked list, using midpoint to split.

This problem is a primitive. Five other Linked List problems call it as a sub-step.

How parikshan turns this into a learning loop

Recommended sequence on parikshan:

1. Solve reverse-linked-list first; the three-pointer dance pairs with slow/fast.
2. In practice mode, AI off, code the slow/fast template. Run public tests.
3. The dynamic private tests will throw: single node, two nodes (where the spec requires the SECOND of the two), three nodes, very long lists. A template that confuses first/second middle fails on the two-node case.
4. Re-solve with the two-pass length-then-walk approach. Compare line counts. The slow/fast version is one line longer, costs the same, and generalises to cycle detection; the two-pass is a dead end.
5. Solve linked-list-cycle next while the slow/fast template is still hot in your fingers.

In the AI-integrated workspace

Generated middle-of-linked-list is correct about 95% of the time on the slow/fast pattern; the 5% failure mode is the wrong loop condition (returns the first middle on even lengths). The agent's reasoning trace will sometimes admit confusion between "first" and "second" middle; insist on the spec.

Verification ritual:

1. Ask: "for [1, 2, 3, 4] does this return 2 or 3?" The agent should answer 3 (the second middle).
2. Trace the empty input. The function must not throw. If the spec allows empty, the function returns null; if not, the function asserts non-empty up front.
3. Ask: "what is the relationship between this and Floyd's cycle detection?" If the agent can answer in one sentence, the abstraction has stuck.

The deeper point: slow/fast is the second canonical Linked List primitive after the three-pointer reversal. Engineers who fluently combine them solve cycle, palindrome, reorder, and sort problems with the same two muscle memories. parikshan stages the cluster exactly to build that combination.