Linked List Midpoint

Given the head of a singly linked list, return the middle node of the list in a single pass, using O(1) extra space.

If the list has an even number of nodes, return the second of the two middle nodes.

Example 1

Input: 1 -> 2 -> 3 -> 4 -> 5

Output: the node with value 3

Explanation: 3 is exactly in the middle of the five-node list.

Example 2

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Output: the node with value 4

Explanation: with six nodes there are two middle candidates (3 and 4); by convention we return the second one, 4.

Constraints

• The number of nodes is in the range [1, 10^5].
• You may not use extra data structures (e.g., arrays, hash maps) to index into the list, and you must find the answer in a single traversal.