Middle of the Linked List

Given the head of a singly linked list, return the middle node. If the number of nodes is odd, return the actual middle; if even, return the second middle node. (LeetCode 876)

Brute force: traverse the entire list to count how many nodes exist, compute middle = count / 2, then traverse again up to that index and return that node.

class Solution {
    public ListNode middleNode(ListNode head) {
        int count = 0;
        ListNode temp = head;

        while (temp != null) {
            count++;
            temp = temp.next;
        }

        int mid = count / 2;
        temp = head;
        for (int i = 0; i < mid; i++) {
            temp = temp.next;
        }

        return temp;
    }
}

Optimal (Tortoise and Hare): slow moves one step at a time, fast moves two steps at a time. When fast reaches the end, slow will be at the middle — for an odd-length list fast reaches the last node so slow is at the middle; for an even-length list fast becomes null so slow is at the second middle. Only one pass, no extra space.

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

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}