Problem Statement

You are given the head of a singly linked list, and your task is to 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: Node with value 3
Explanation: The middle node of the list is 3.

Example 2:

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

Constraints:

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

Approach 1: Count Nodes (Two Pass)

• Traverse the list once to count the total number of nodes, say n.
• Calculate the middle index as n / 2.
• Traverse the list again up to the middle index and return that node.

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

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

        // First pass: count the nodes
        while (current != null) {
            count++;
            current = current.next;
        }

        // Calculate middle index
        int middle = count / 2;

        current = head;
        // Second pass: move to middle
        for (int i = 0; i < middle; i++) {
            current = current.next;
        }

        return current;
    }
}

Time Complexity: O(n) – two traversals of the linked list.
Space Complexity: O(1) – only a few pointers are used.

Approach 2: Fast and Slow Pointers (One Pass)

This is the most efficient method. We use two pointers:

1. slow moves one step at a time.
2. fast moves two steps at a time.

• When fast reaches the end, slow will be at the middle node.

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;
        }

        // Slow is now at the middle node
        return slow;
    }
}

Time Complexity: O(n) – single pass through the list.
Space Complexity: O(1) – only two pointers are used.

Why Fast and Slow Pointers Work

• When fast moves two steps for every one step of slow, by the time fast reaches the end of the list:
  • slow has moved half the distance.
• This automatically handles even and odd length lists:
  • Odd length → slow points exactly to the middle.
  • Even length → slow points to the second middle node, as required by the problem.