Description: Given the head of a singly linked list, return the middle node of the linked list.

Brute-force Approach

Iterate through the linked list counting the number of nodes. Then, iterate through the list again and return the count / 2th node.

Time: O(n)

Space: O(1)

Optimal Approach

Use tortoise and hare algorithm with two pointers, one moving one step at a time and the second one moving two steps at a time. When the fast pointer reaches the end, the first pointer will be at the middle of the list.

Time: O(n)

Space: O(1)