Middle of the Linked List

Description

Middle of the Linked List
Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints:

• The number of nodes in the list is in the range [1, 100].
• 1 <= Node.val <= 100

Brute Force Approach: Two Pass (Count & Advance)

Mental Model: First, measure how long the list is. Second, walk to the middle (length / 2).

1. Iterate through the entire list to count the total number of nodes ($N$).
2. Calculate the middle index as $N/2$.
3. Reset your pointer to head and step forward $N/2$ times.

class Solution {
    public ListNode middleNode(ListNode head) {
        int length = 0;
        ListNode temp = head;
 
        // 1st Pass: Find total count
        while (temp != null) {
            length++;
            temp = temp.next;
        }
 
        // 2nd Pass: Move to the middle node
        temp = head;
        for (int i = 0; i < length / 2; i++) {
            temp = temp.next;
        }
 
        return temp;
    }
}
 

• Time Complexity: $\mathcal{O}(N)$ — iterates over the list twice.
• Space Complexity: $\mathcal{O}(1)$ — uses a few pointer variables.

---

Most Optimized Approach: Two Pointers (Slow & Fast / Tortoise & Hare)

Mental Model: Imagine two runners on a track starting at the same time. If one runner is twice as fast as the other, by the time the fast runner reaches the finish line, the slow runner will be exactly halfway through.

1. Initialize slow and fast pointers at head.
2. Move slow by 1 step (slow = slow.next) and fast by 2 steps (fast = fast.next.next).
3. When fast reaches the end (fast == null or fast.next == null), slow will be right at the middle.

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
 
        // Move fast by 2 steps and slow by 1 step
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
 
        return slow; // Points to the middle node
    }
}
 

• Time Complexity: $\mathcal{O}(N)$ — single pass (scans the list once).
• Space Complexity: $\mathcal{O}(1)$ — uses constant extra space.