Sweaty Imposter

Middle of the Linked List

EasyFast & Slow Pointers (Floyd's)JuniorOpen on LeetCodeUpdated

You're given the head of a non-empty singly linked list. Return the middle node. With an odd number of nodes there is exactly one middle; with an even number there are two, and you must return the second one. For n nodes that is the node at 0-based index n / 2, rounded down. You aren't told n, so try to find the middle in a single pass.

Examples

head = [1,2,3,4,5] returns node 3

12345null
Two nodes on each side of the middle.

There are 5 nodes, so the middle is the third, value 3 (index 2), with two nodes on each side. Returning it hands back the rest of the list, [3,4,5].

head = [1,2,3,4,5,6] returns node 4

123456null
Two middles, 3 and 4; the second one is returned.

There are 6 nodes, so values 3 and 4 (indices 2 and 3) are both middles. The problem asks for the second one, value 4.

Constraints

  • 1 <= n <= 100

Hints

Hint 1

What if one pointer moved twice as fast as another through the list?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Move slow one node and fast two nodes per step, stopping when fast is null or fast.next is null. By then slow has taken n / 2 steps (rounded down), so it sits at the middle, and on even lengths this stopping rule lands on the second middle. It's one pass with two references and no length count.

Time

O(n)

Space

O(1)

Pitfall

The loop condition picks which middle you get. `while fast and fast.next` returns the second middle (node 4 in [1,2,3,4,5,6]); `while fast.next and fast.next.next` stops a step early and returns node 3, which is wrong here.

Solutions

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
Drill This