Find the Middle of a Linked List (No length)

To find the middle of a singly linked list without knowing its length, I would implement the classic 'Fast and Slow' pointer approach, which allows us to solve this in a single traversal. First, I initialize two pointers, both starting at the head of the list. The slow pointer will advance one node at a time, while the fast pointer advances two nodes at a time. As we iterate through the loop, checking if the fast pointer and its subsequent node exist, the fast pointer essentially moves twice as fast as the slow pointer. Consequently, when the fast pointer reaches the end of the list, the slow pointer will naturally be positioned exactly at the middle node. For example, if the list has five nodes, the fast pointer traverses to the end in three jumps, placing the slow pointer at index two, which is the correct middle. If the list has an even number of nodes, say four, the fast pointer will hit null after the fourth node, leaving the slow pointer at the third node, which is standard behavior for returning the second middle element. This solution achieves O(n) time complexity since we visit each node once, and crucially, it uses O(1) space complexity because we only store two references regardless of list size. This aligns perfectly with the efficiency standards expected at Google, avoiding unnecessary memory allocation or multiple passes.