Middle of the Linked List – Optimal Two Pointer Approach (Python)

Middle of the Linked List – Optimal Two Pointer Approach

Finding the middle of a singly linked list efficiently is a common interview problem. In this solution, we use the slow and fast pointer technique to determine the middle node in a single traversal.

Intuition Behind the Approach

We maintain two pointers:

• Slow Pointer (p1) → moves one step at a time
• Fast Pointer (p2) → moves two steps at a time

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

Visual Representation

Python Implementation

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p1 = p2 = head

        while p2 and p2.next:
            p1 = p1.next
            p2 = p2.next.next

        return p1

  

Why This Works

Since the fast pointer moves twice as fast as the slow pointer, by the time it reaches the end of the list, the slow pointer has covered half the distance — landing exactly at the middle.

For even-length lists, this approach correctly returns the second middle node, which aligns with the problem’s requirement.

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Reference Implementation

You can find the complete solution on GitHub:
https://github.com/RohitSingh-04/Python-Solutions/blob/main/LC876.py