Which method finds the middle element of a singly linked list in one pass?

• A. Slow and fast pointers: move slow by 1 and fast by 2; when fast reaches end, slow is middle; O(n)
• B. First compute length, then move to length/2 from head.
• C. Push nodes onto a stack until you reach the middle; pop to middle; O(n) extra space
• D. Return the node after head.

Answer: (A)

Finding the middle in one pass uses the two-pointer idea: have a slow pointer move one node at a time and a fast pointer move two nodes at a time. As you traverse, the fast pointer quickly reaches the end while the slow pointer has advanced roughly half as many steps. When the fast pointer reaches the end, the slow pointer lands at the middle. This gives you the middle in a single traversal with O(n) time and only O(1) extra space, since you’re just keeping two references.

This works for lists of any length: for odd-length lists, the slow pointer ends up exactly at the middle element; for even-length lists, you end up at the lower of the two middle positions in the usual implementation, which is still a valid “middle” in many contexts. Edge cases like an empty list or a single node are naturally handled by the pointers reaching their end conditions.

Other approaches require extra passes or extra storage: computing the length first is two passes; using a stack needs O(n) extra space; simply returning the node after head gives a position that isn’t the middle in general.