Fold Many Times
One fold reorders a list like this: the first node, then the last, then the second, then the second to last, and so on, working inwards from both ends. So 1 -> 2 -> 3 -> 4 -> 5 becomes 1 -> 5 -> 2 -> 4 -> 3.
Fold the list times times, each fold starting from the result of the one before, and return the head. times can be as large as a billion, far too many to carry out one by one. The list is passed in as head.
Linked lists appear in the tests as the list of their values, like [1,2,3]. Each node is a ListNode with .val and .next; the class is already defined for you.
Example 1
The first fold gives 1, 5, 2, 4, 3. Folding that again gives 1, 3, 5, 4, 2.
Example 2
One fold of four nodes: first, last, second, third.
Example 3
With three nodes the second fold undoes the first, and so does every later pair of folds.
Constraints
0 <= number of nodes <= 40-100 <= node.val <= 1000 <= times <= 10**9
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.