☕ DSA Java Articles

Topics › Linked List › Medium Problems of LL

Find Middle of Linked List

Easy TUF ID 448 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the head of a singly linked list. Return the middle node of the list. When the list has an even number of nodes there are two middle nodes, and you must return the second of them. The answer is the node itself, not just its value, so the caller can keep walking the list from that point.

Constraints: 1 ≤ n ≤ 100 in the LeetCode version, node values fit in an int. The Java solutions also accept an empty list and return null for it.

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

Example 1

head   = 1 -> 2 -> 3 -> 4 -> 5
answer = the node holding 3        // two nodes on each side of it

Example 2

head   = 1 -> 2 -> 3 -> 4 -> 5 -> 6
answer = the node holding 4        // the middles are 3 and 4; the second one is asked for

A useful way to pin down “the middle” precisely: with 0-based positions, the requested node is at index n / 2 (integer division). For n = 5 that is index 2, the third node. For n = 6 it is index 3, the fourth node. Both approaches below are just different ways of reaching index n / 2.

Approach 1: Brute force, count then walk

Intuition. With an array you would simply return a[n / 2]. A linked list gives you neither its length nor random access, so you have to earn both by walking. The most direct plan is therefore two passes: the first pass counts the nodes, the second pass starts again at the head and takes exactly n / 2 steps. Nothing about this is clever, and it is already linear time, which is the best possible because you cannot find the middle without at least reaching the end.

Algorithm.

  1. Walk the whole list once and count the nodes into len.
  2. Start a pointer mid at the head.
  3. Move mid forward len / 2 times.
  4. Return mid.
static ListNode bruteForce(ListNode head) {
    int len = 0;
    for (ListNode t = head; t != null; t = t.next) len++;
    ListNode mid = head;
    for (int i = 0; i < len / 2; i++) mid = mid.next;   // index len / 2 is the (second) middle
    return mid;
}

Complexity. Time O(n): n steps to count plus n / 2 steps to walk back to the middle, about 1.5n node visits in total. Space O(1): one counter and one pointer.

A variation stores every node reference in an ArrayList during a single pass and then returns list.get(n / 2). That avoids the second walk but costs O(n) extra memory, which is a poor trade for a problem that can be solved in constant space.

So why look further? The count-then-walk method needs the whole list to be traversed before it can even start looking for the answer. The next approach finds the middle during a single traversal, and the pattern it uses (two pointers moving at different speeds) shows up again in cycle detection, palindrome checks, list merge sort and reordering problems. It is worth learning here, where it is easiest to reason about.

Approach 2: Optimal, tortoise and hare

Intuition. Put two pointers at the head. Each round, slow moves one node and fast moves two nodes. After k rounds, slow is at index k and fast is at index 2k. The moment fast cannot go any further it has covered the whole list, so 2k is about n, which means slow is at about n / 2. The ratio of the two speeds performs the division by two for you, and you never need to know n explicitly.

The exact loop condition decides which middle you get, so it is worth checking both parities carefully. The loop keeps going while fast != null && fast.next != null, that is, while fast can legally take two more steps.

In both cases slow lands on index n / 2, exactly the node the brute force reaches.

If a problem asks for the first middle of an even list instead (which is what you want when splitting a list into two halves, as in merge sort, where cutting a two-node list after its second middle would never make it smaller), change the condition to fast.next != null && fast.next.next != null. Then slow stops one node earlier on even lengths and stays the same on odd lengths.

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) {   // fast can still take two steps
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

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

round slow fast can fast take two steps?
start 1 1 yes, 2 exists
1 2 3 yes, 4 exists
2 3 5 yes, 6 exists
3 4 null no, stop

The method returns the node holding 4, the second middle. On 1 -> 2 -> 3 -> 4 -> 5 the rounds end with slow on 3 and fast on 5, and since 5 has no successor the loop stops there.

Complexity. Time O(n): the loop runs about n / 2 times and does constant work per round. Space O(1): two pointers.

Note that the total number of pointer hops is roughly the same as in the brute force, because fast still touches every other node and slow touches half of them. The gain is not raw speed; it is that the answer is found in one traversal, with no length variable, and the technique carries over to many harder problems.

Edge cases and pitfalls