Nodes are instances of the provided ListNode class (fields val and next). Write middle_node(head) that returns the middle node of a non-empty list. When the list has an even length there are two middles; return the second one.
Return the node itself (the tests check it is one of the original nodes), and don't modify the list.
1 -> 2 -> 3 -> 4 -> 5 middle is the node 3
1 -> 2 -> 3 -> 4 -> 5 -> 6 middle is the node 4 (the second of 3 and 4)
7 middle is the node 7
Constraints: 1 <= length <= 2 * 10^5. Do it in one pass with O(1) extra memory: no copying the nodes into a Python list.
Show hint
start slow and fast at head and, while fast and fast.next, move slow one step and fast two steps; when fast runs out, slow is at the middle.