Reorder a list from both ends
You get head, the first node of a linked list, or None if the list is empty. Each node is a ListNode with a value (node.val) and a link (node.next) to the node after it.
Rearrange the nodes so the order alternates between the front and the back: the first node, then the last, then the second, then the second-to-last, and so on, until every node is placed once.
Work in place: change only the next links. Do not change any node's val and do not create nodes, because the tests check that the original node objects end up in the new order. The head stays first, so return nothing: the tests read the list from the same head after the call. An empty list needs no change.
Examples write a linked list as the list of its values: [2, 4, 6, 8] means 2 → 4 → 6 → 8.
head = [2, 4, 6, 8]Outputhead now reads [2, 8, 4, 6]First 2, last 8, second 4, then 6, the only node left.
head = [10, 20, 30, 40, 50]Outputhead now reads [10, 50, 20, 40, 30]With an odd count, the middle node 30 ends up last.
head = [7, 8, 9]Outputhead now reads [7, 9, 8]0 ≤ number of nodes ≤ 5 × 104
Node values are integers and may repeat.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.