Middle of Linked List

Problem Link

876. Middle of the Linked List – LeetCode

Problem Statement

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.

Examples

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: There are two middle nodes (3 and 4), and we return the second one.

Constraints

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

• 1 <= Node.val <= 100

Intuition

To find the middle node of a linked list efficiently, we can use the fast and slow pointer technique:

• slow pointer moves 1 node at a time

• fast pointer moves 2 nodes at a time

When the fast pointer reaches the end, the slow pointer will be at the middle of the list.

Approach: Fast and Slow Pointer

1. Initialize two pointers: slow = head, fast = head.

2. Traverse the list:

   • Move slow one step.

   • Move fast two steps.

3. Stop when fast == null or fast.next == null.

4. Return the slow pointer (it will point to the middle).

Java Code

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

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

        return slow;
    }
}

Time and Space Complexity

Dry Run

Input:

head = [1,2,3,4,5]

Pointers Progress:

Output: Node with value 3

Alternate Approach

Array-based solution (less efficient):

• Store nodes in an array or list.

• Return nodes[n / 2].

public ListNode middleNode(ListNode head) {
    List<ListNode> list = new ArrayList<>();
    while (head != null) {
        list.add(head);
        head = head.next;
    }
    return list.get(list.size() / 2);
}

Time: O(n), Space: O(n)

Conclusion

This problem is a classic example of the fast and slow pointer pattern, often used in linked list problems for:

• Detecting cycles

• Finding middle elements

• Splitting lists

It offers an elegant O(n) time and O(1) space solution.