Problem Statement in English

You’re give a linked list node head. Your task is to return the middle node of the linked list.

Approach

The naive and approach would be to iterate over the array, and calculate the number of nodes in it. Then divide that number by 2, and iterate over the array again to find the node with that index.

But we can do better.

Enter the Fast and Slow Pointer Technique, also known as Floyd’s Tortoise and Hare Algorithm.

The logic here is stupidly simple. We have 2 pointers, one that moves 1 step at a time, and another that moves 2 steps at a time.

Now think about it - when the faster pointer reaches the end of the linked list, the slower pointer will be at the middle of the linked list!

That’s pretty much it.

Solution in Python


class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = head
        slow = head
        
        # check that `fast` exists, and that `fast.next` exists
        while fast and fast.next:
            assert slow != None
            slow = slow.next

            fast = fast.next.next
        return slow

Note: Why do we check for the existence of fast.next?

Because if fast.next doesn’t exist, then neither will fast.next.next, and then we’ll end up with a nasty null pointer dereference error. Eww.

Complexity

  • Time: $O(n)$
    Since we iterate over atmost $n$ elements.

  • Space: $O(1)$
    Since we use only 2 pointer variables.

And we are done.