Middle of the Linked List (LC 876)

Pattern: Fast & Slow Pointers (Tortoise and Hare)
Difficulty: Easy
Key Concept: Move fast two steps per iteration and slow one step; when fast reaches the end, slow lands on the middle (second middle when length is even).

Problem Statement

You are given the head of a singly linked list. Return the middle node of the list.

If the list has an even number of nodes, there are two middle nodes; return the second middle node (the one closer to the tail).

Input: head — reference to the first ListNode of a singly linked list (each node has int val and ListNode next).

Output: The ListNode that is the middle (or second middle) of the list.

Constraints (typical): The number of nodes is in the range [1, 100]. 1 <= Node.val <= 100.

---

1. Algorithm & Pseudocode

Brute force (two passes)

1. First pass: walk from head to the end, counting nodes → length n.
2. Second pass: advance (n / 2) steps from head (0-based: skip first n/2 nodes).
3. Return the node you stop on.

Optimal (fast & slow pointers)

1. Initialize slow = head, fast = head.
2. While fast is not null and fast.next is not null:
   • slow = slow.next
   • fast = fast.next.next
3. Return slow.

Why this gives the second middle when n is even: After the loop, fast is null. For even length, slow has moved n/2 steps from the start, which is exactly the second middle (1-based positions n/2 and n/2 + 1 → we want index n/2 in 0-based terms after n/2 moves from head).

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why two passes work: Counting tells you how far the middle is. Walking exactly half the list from the start is correct but needs an extra traversal.

Why fast/slow works: Each time slow moves 1, fast moves 2, so fast covers twice the distance. When fast hits the end, slow has gone half as far as the “full” walk that fast represents — that is the middle region.

Why check fast != null && fast.next != null: If fast.next is null, fast.next.next would throw. If fast is null, we are done. This pattern safely handles both odd and even lengths.

Odd vs even: For odd n, fast ends on the last node (fast.next == null). For even n, fast ends as null after jumping past the last node. In both cases, slow is at the required middle (second middle when even).

---

3. The Dry Run

Assume nodes are 1 -> 2 -> 3 -> 4 -> 5 (values shown; null means end).

Step	Condition (fast, fast.next)	slow (value)	fast (value)	Action
Init	—	1	1	—
1	both non-null	2	3	advance slow once, fast twice
2	both non-null	3	5	advance again
3	fast.next is null	—	—	exit loop

Result: slow points to node with value 3 (the only middle).

List 1 -> 2 -> 3 -> 4 -> 5 -> 6:

Step	Condition	slow (value)	fast (value)	Notes
Init	—	1	1
1	OK	2	3
2	OK	3	5
3	OK	4	null	fast = fast.next.next from 5
4	fast is null	—	—	exit

Result: slow is at value 4 (second of two middles: 3 and 4).

---

4. Java Solution

Brute Force

/**
 * Definition for singly-linked list node (LeetCode style).
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode middleNode(ListNode head) {
        int n = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            n++;
        }
        ListNode cur = head;
        for (int i = 0; i < n / 2; i++) {
            cur = cur.next;
        }
        return cur;
    }
}

Time: O(n) — two full passes in the worst case.
Space: O(1) — only a few counters and references.

Optimal

class Solution {
    public 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: O(n) — single pass.
Space: O(1).

---

5. The “Java vs. Others” Edge

• No pointer arithmetic: In C/C++ you might think in terms of addresses; in Java you only hold references to objects. You write fast.next.next, not fast->next->next (C++). The idea is the same: follow two links.
• Null safety: Dereferencing a null reference throws NullPointerException. In C/C++, a bad pointer can cause a segfault. The while (fast != null && fast.next != null) guard is the idiomatic way to avoid stepping off the list.
• LinkedList vs ListNode: Java’s java.util.LinkedList is a collection class with different APIs and internal structure. LeetCode problems use a simple ListNode type; your solution should use that, not LinkedList<Integer>.
• Returning a node: You return the reference to the middle ListNode; the rest of the list is still reachable through next — no copying required.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(1)	Two traversals; easy to reason about.
Optimal	O(n)	O(1)	One traversal; standard fast/slow template.