Topics › Linked List › Medium Problems of LL

Middle of a LinkedList [TortoiseHare Method]

Easy TUF ID 2810 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given the head of a singly linked list. Return the middle node. When the list has an even number of nodes there are two middle nodes; return the second one, as the LeetCode version requires. Return the node itself, not just its value, so the caller can continue from it. An empty list has no middle; return null.

Constraints: 0 ≤ n ≤ 10^5 nodes, values fit in a 32-bit signed integer, no cycles.

Example 1

list = 1 -> 2 -> 3 -> 4 -> 5
answer = node 3                // odd length, one middle

Example 2

list = 1 -> 2 -> 3 -> 4 -> 5 -> 6
answer = node 4                // even length, the second of the two middles 3 and 4

Example 3

list = 1 -> 2
answer = node 2                // the second of the two middles 1 and 2

In 0-based terms the answer is the node at index n / 2 (integer division). For n = 5 that is index 2, the node 3; for n = 6 it is index 3, the node 4.

The node type is the standard one with an int val and a ListNode next reference.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Approach 1: Brute force, count then walk

Intuition. The middle is defined by position, and the position depends on the length. A linked list does not know its length, so the direct method is to count the nodes first, compute the target index n / 2, and walk there in a second pass. It is correct, simple and linear; its only weakness is that it reads the list twice.

Algorithm.

1. Traverse once and count the nodes into n.
2. Set temp = head and advance it n / 2 times.
3. Return temp.

static ListNode bruteForce(ListNode head) {
    int n = 0;
    for (ListNode t = head; t != null; t = t.next) n++;
    ListNode temp = head;
    for (int i = 0; i < n / 2; i++) temp = temp.next;   // 0-based index n / 2 is the (second) middle
    return temp;
}

Complexity. Time O(n): n steps for the count plus n / 2 for the walk, about 1.5n in total. Space O(1).

For the empty list n = 0, the second loop does not run, and temp = head = null is returned. For a single node, n / 2 = 0 and the head is returned.

Approach 2: Optimal, tortoise and hare

Intuition. Picture two runners starting at the head. The tortoise (slow) moves one node per step; the hare (fast) moves two. At every moment the hare has covered exactly twice the distance of the tortoise. So when the hare reaches the end of the list, the tortoise has covered half of it and is standing on the middle. One pass, no counting, two references.

The precise claim: after k iterations, slow is at index k and fast is at index 2k. The loop stops when fast is null or fast.next is null, meaning index 2k is at or past the last node. For odd n = 2m + 1, the loop stops with fast on the last node (index 2m), so k = m = n / 2. For even n = 2m, the loop stops with fast == null after index 2m is passed, so k = m = n / 2. Either way slow is at index n / 2, which is exactly the second middle.

Algorithm.

1. Set slow = head and fast = head.
2. While fast != null and fast.next != null: move slow one step and fast two steps.
3. Return slow.

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

Complexity. Time O(n): the loop runs n / 2 times, each doing constant work, and no counting pass is needed. Space O(1).

Dry run on 1 -> 2 -> 3 -> 4 -> 5 -> 6:

slow ends on node 4, the second middle. On 1 -> 2 -> 3 -> 4 -> 5 the third iteration never happens because after iteration 2 fast is on node 5 whose next is null; slow stays on 3.

The loop condition fast != null && fast.next != null is checked in that order deliberately. If fast is null, the && short-circuits and fast.next is never evaluated, so there is no NullPointerException on even-length lists where fast runs off the end.

The empty list works without a special case: fast starts as null, the loop does not run, and slow, also null, is returned.

Variant: the first middle

Intuition. Some problems want the first of the two middles for an even length, for example when a list is to be split into two halves of equal size, or when checking a palindrome. The only change is the stopping rule: fast should stop one node earlier. Starting from the same place and testing fast.next and fast.next.next instead of fast and fast.next achieves that. For odd lengths both variants land on the same node.

Algorithm.

1. If head is null, return null (the loop below dereferences fast).
2. Set slow = head, fast = head.
3. While fast.next != null and fast.next.next != null: advance slow by one and fast by two.
4. Return slow.

static ListNode optimalFirstMiddle(ListNode head) {
    if (head == null) return null;
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Complexity. Time O(n), space O(1).

In 0-based terms this returns index (n - 1) / 2: node 3 for six nodes, node 1 for two nodes, and the same as optimal whenever n is odd. The test file verifies both variants against position-based oracles (n / 2 and (n - 1) / 2) and asserts, for odd lengths, that they return the very same node object.

Why this pattern matters

The tortoise-hare idea is used far beyond finding the middle. With the same two pointers you can detect a cycle (the hare laps the tortoise), find where a cycle begins, split a list for merge sort, delete the middle node in one pass, and check a palindrome by reversing the second half. In every case the reason it works is the same invariant: the hare’s distance from the start is always exactly twice the tortoise’s.

Between the two approaches, both are linear and constant-space, so the asymptotic complexity is identical. The two-pointer version is preferred because it makes a single pass (useful when the list is streamed or expensive to traverse) and because it generalises to the problems above, where the count-and-walk method does not apply at all.

Edge cases and pitfalls

• Empty list. Return null. optimal handles it with no special case; optimalFirstMiddle needs the explicit check because it reads fast.next before testing fast.
• Single node. It is its own middle; both loops end immediately.
• Two nodes. The second middle is node 2, the first middle is node 1. This is the smallest case where the two variants differ.
• Wrong loop condition. Testing only fast != null lets fast.next.next throw when fast is the last node. Testing only fast.next != null throws when fast itself is null. You need both, with the fast != null test first.
• Off-by-one between the two middles. Decide which middle the problem wants before writing the loop and verify on a two-node and a four-node list.
• Identity versus value. Return the node, and compare nodes with == in tests. 7 -> 7 -> 7 -> 7 has four nodes with equal values; the correct answer is the third node object, not “a node with value 7”.
• Cycles. With a cycle the hare never reaches null and the loop runs forever; the problem rules cycles out, and detecting them is the next application of the same two pointers.

Related problems

• Detect a loop in LL uses the same two pointers to detect that the hare laps the tortoise.
• Find the starting point in LL extends loop detection to locate the cycle’s entry.
• Delete the middle node in LL combines this finder with a one-pass deletion.
• Check if LL is palindrome or not finds the middle and reverses the second half.
• Sort LL splits the list at the middle for merge sort.
• Find the length of the Linked List is the counting pass used by the brute force here.