FunctionRacerProblemsRace

Fold Many Times

HardLinked listsPython, JavaScript, TypeScript, Java, C++

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

head [1,2,3,4,5]
times 2
returns [1,3,5,4,2]

The first fold gives 1, 5, 2, 4, 3. Folding that again gives 1, 3, 5, 4, 2.

Example 2

head [1,2,3,4]
times 1
returns [1,4,2,3]

One fold of four nodes: first, last, second, third.

Example 3

head [1,2,3]
times 1000000000
returns [1,2,3]

With three nodes the second fold undoes the first, and so does every later pair of folds.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Linked lists problems