Middle of the Linked List

Given the head of a singly linked list, return its middle node. If the list has an even number of nodes, there are two middle nodes. Return the second one.

LeetCode: 876. Middle of the Linked List

Example 1

Text

Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 3   (LeetCode returns the list starting there: 3 -> 4 -> 5)

Example 2

Text

Input:  1 -> 2 -> 3 -> 4 -> 5 -> 6
Output: 4   (the middles are 3 and 4; take the second)

With n nodes, the middle is at index n / 2 (counting from 0): 5 / 2 = 2 gives node 3, and 6 / 2 = 3 gives node 4.

Brute force: count, then walk

Walk the list once to count its nodes.
Walk n / 2 steps from the head.

The method returns the node it stops at. Because Java returns a reference, the result is the middle node and everything after it, which matches LeetCode's signature. A list node is an object with a mutable next field, and null marks the end of the list.

Java

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

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

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        System.out.println(show(middleNode(fromArray(1, 2, 3, 4, 5))));
        System.out.println(show(middleNode(fromArray(1, 2, 3, 4, 5, 6))));
    }
}

Output

[3, 4, 5]
[4, 5, 6]

Time: O(n) with two passes (about 1.5n steps). Space: O(1).

The second loop runs fewer than len times, so cur is never null when cur.next is read.

Optimal: fast and slow pointers

Move slow one node per step and fast two nodes per step. When fast can't take two more steps, slow has covered half the distance and is at the middle.

Walkthrough with 1 -> 2 -> 3 -> 4 -> 5 -> 6:

step	slow	fast	can fast move two more?
start	1	1	yes (2, 3)
1	2	3	yes (4, 5)
2	3	5	yes (6, then null)
3	4	null	stop

slow ends at 4, the second middle.

Java

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

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

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode node) {
        return node == null ? "null" : String.valueOf(node.val);
    }

    public static void main(String[] args) {
        System.out.println(show(middle(fromArray(1, 2, 3, 4, 5))));
        System.out.println(show(middle(fromArray(1, 2, 3, 4, 5, 6))));
        System.out.println(show(middle(fromArray(9))) + " " + show(middle(null)));
    }
}

Output

3
4
9 null

Time: O(n) in a single pass. Space: O(1).

The loop condition fast != null && fast.next != null means "fast exists and has a next node". The && operator stops at the first false operand, so fast.next is never read when fast is null. Inside the loop, fast jumps two nodes to fast.next.next, which may be null.

Both pointers are ordinary references to the same list, and moving them does not change the list. The result is the middle node itself, so the caller sees the nodes from the middle to the end without any copying.

Edge cases

Empty list: null.
One node: that node.
Two nodes: the second node, since the second middle is returned for even lengths.
First middle instead of second: change the loop condition to fast.next != null && fast.next.next != null.