Nodes are instances of the provided ListNode class (fields val and next). Write reverse_list(head) that reverses the list in place by re-pointing the next fields, and returns the new head. An empty list is None.
Don't create new nodes: the tests check that the nodes you return are the original ones. Lists can have 200,000 nodes, so a recursive solution will blow Python's recursion limit. Aim for O(n) time and O(1) extra memory.
7 -> 3 -> 9 becomes 9 -> 3 -> 7
4 becomes 4
(empty) stays (empty)
Show hint
Walk the list once, keeping track of the node before the current one; save the current node's next before you re-point it.