Given the head node of a singly linked list, rearrange the nodes so that the order becomes: first node, last node, second node, second last node, third node, third last node, and so on. You must not modify the values in the nodes; only the node connections may be changed. Return the head of the reordered linked list.
Example 1
Input: ListNode(10, ListNode(20, ListNode(30, ListNode(40))))
Output: [10, 40, 20, 30]
Explanation: First node is 10, last is 40, second is 20, second last is 30.
Example 2
Input: ListNode(5, ListNode(6, ListNode(7, ListNode(8, ListNode(9)))))
Output: [5, 9, 6, 8, 7]
Explanation: First node is 5, last is 9, second is 6, second last is 8, third is 7.
Constraints
Case 1
Input: ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6))))))
Expected: [1, 6, 2, 5, 3, 4]
Case 2
Input: ListNode(100)
Expected: [100]
Case 3
Input: ListNode(7, ListNode(8, ListNode(9)))
Expected: [7, 9, 8]
Case 4
Input: ListNode(2, ListNode(4, ListNode(6, ListNode(8))))
Expected: [2, 8, 4, 6]