A captioning service stores incoming audio chunks as a singly linked list. Product wants the second editor pane to start at the middle chunk — the later middle if the take is even-length — without a counting pass to learn how many chunks landed. The intern counted nodes, then walked length / 2. Correct. Two full passes of a take that was already tens of thousands of chunks by the time the producer hit split.

Middle of the Linked List asks for that node — the second middle when the length is even. You return a node, not an index into an array you do not have.

This is an interview writeup, not a two-pointers lecture. The linked list post owns splice and why get(i) walks. The two pointers post owns the slow/fast move rule. Here we only care about a 2:1 step ratio that parks slow on the (second) middle when fast falls off the list.

The problem

Given the head of a singly linked list, return the middle node. If the list has even length, there are two middles — return the second. A one-node list returns that node. Empty is not the usual case.

1 → 2 → 3 → 4 → 5 → null        →  3 → 4 → 5
1 → 2 → 3 → 4 → 5 → 6 → null    →  4 → 5 → 6
1 → null                         →  1
1 → 2 → null                     →  2

A node is the usual two fields:

final class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

Note: You return the node object. Its next chain is the suffix from the middle onward. Copying values into an array and indexing length / 2 answers the value and allocates a second list of them — the same identity trap as Reverse Linked List.

Two passes: count, then walk length / 2

First walk counts length L. Second walk takes L / 2 steps from head. Integer division is the second-middle rule: five nodes walk two steps (land on 3); six nodes walk three (land on 4).

ListNode middleNodeTwoPass(ListNode head) {
    int length = 0;
    for (ListNode p = head; p != null; p = p.next) {
        length++;
    }
    ListNode current = head;
    for (int i = 0; i < length / 2; i++) {
        current = current.next;
    }
    return current;
}

At a handful of chunks this is a rounding error. At a long take you paid two full walks for a question half speed answers in one: when the faster pointer hits null, the slower one is already at the middle.

One pass: fast takes two, slow takes one

Both start at head. Each iteration, fast takes two nexts and slow takes one. When fast cannot take two steps, slow sits on the middle — the second middle when the length is even.

This is half speed, not a gap. Remove Nth from End parks a pointer n ahead, then walks both at the same speed so the lagging one lands before a chosen offset from the tail. Here there is no n to stage: the 2:1 ratio is the invariant.

Walk odd length 1 → 2 → 3 → 4 → 5:

start:  slow=1  fast=1

step 1: slow=2  fast=3
step 2: slow=3  fast=5     fast.next is null, stop

return 3

Even length is the prompt’s second-middle rule. Walk 1 → 2 → 3 → 4 → 5 → 6. The last iteration moves slow from 3 to 4 and sends fast off the list:

start:  slow=1  fast=1

step 1: slow=2  fast=3
step 2: slow=3  fast=5
step 3: slow=4  fast=null  (fast was 5; 5.next.next is null)

return 4   (second middle)

Linked List Cycle uses the same two speeds on next. That writeup asks whether they ever land on the same node after moving — a loop. This writeup never compares them: when fast hits null, slow is the middle. The list is assumed to end.

The Java is that walk. Guard fast and fast.next before each double step so you never dereference null.

ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Time is O(n) — fast visits each node at most once. Space is O(1) besides the two pointers. The counting walk is also O(n) time and still pays a second pass; slow and fast finish in one.

Note: Requiring fast.next.next != null returns the first middle. The loop is fast != null && fast.next != null so the last even-length step still runs: slow walks onto 4 while fast steps off 5. One node: fast.next is null, the loop never runs, you return head. Two nodes: one iteration, you return the second. No special cases.

What interviewers usually poke next

  • First middle on even length. Change the stop condition so slow does not take that last step, or start fast one node ahead. Say which middle the prompt asked for before you change it.
  • Split the list into two halves. The middle you return is the head of the second half. You still need the predecessor of that node to cut next, or a dummy so the first half has a handle.
  • Palindrome list. Find the middle, reverse the second half, compare. Reverse Linked List is that rewire; this writeup is only the split.
  • Empty list. The usual prompt guarantees at least one node. If head is null, both pointers are null, you return null. In production you would ask.
  • A cycle in the list. Then fast never hits null. That is Linked List Cycle, not this job. Do not mix the meeting test into the midpoint walk.

You are done with this problem when you can land on 4 in 1 → 2 → 3 → 4 → 5 → 6 without counting, and you can say why a gap of n is a different two-pointer walk than half speed.