Problem 8.2 · Linked ListsEasy

Middle of the Linked List

What it teaches: Fast and slow pointers find the middle in one pass, without counting the length first.

Practise it on judges as “Middle of the Linked List”.

The problem

Return the middle node of a singly linked list. With two middle nodes (even length), return the second one.

Example 1

Input: head = [1, 2, 3, 4, 5]
Output: [3, 4, 5]

The returned node is 3 (shown with the rest of the list).

Example 2

Input: head = [1, 2, 3, 4, 5, 6]
Output: [4, 5, 6]

Constraints

1 ≤ number of nodes ≤ 100

Pattern clues in the wording

→ Middle of a list without knowing its length
→ One pass

These clues point to Fast and Slow Pointers: Move one pointer one step and another two steps; their meeting (or the fast one finishing) reveals cycles and middles.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        return slow;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	head = [1,2,3,4,5]	[3,4,5]
2	head = [1,2,3,4,5,6]	[4,5,6]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Count, then walk half · O(n)2. Optimal: fast and slow · O(n)

Count, then walk half

Time O(n) Space O(1)

Count n, then walk n / 2 steps.

Approach 1

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

Verdict: Two passes; fine, but the next approach does it in one.

Optimal: fast and slow

Time O(n) Space O(1)

slow +1, fast +2 while fast and fast.next exist. Return slow.

Approach 2

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;
    }
}

Verdict: One pass.

Before you submit

Edge cases and common mistakes

Test these inputs

One node
Two nodes (returns the second)
Odd and even lengths

Mistakes people make

Loop condition fast.next.next != null returns the first middle for even lengths (the problem wants the second).

Interview

Follow-up questions

How would you return the first middle for even lengths?

Command Palette