Reorder a List From Both Ends

MediumLinked listTwo pointers183 tests

You are given head, the first node of a singly linked list. Call its nodes L0, L1, L2, ..., Lk from first to last.

Change the next links so the nodes come in this order:

L0, Lk, L1, Lk-1, L2, Lk-2, ...

That is: the first node, then the last node, then the second node, then the second-last node, and so on, until every node is used once.

Note

Change the list in place. Do not create new nodes and do not change any val.
Your function returns nothing. The first node stays first, so after your function ends, the judge reads the list starting from the same head node it gave you.
The last node of the new order must have next set to null (None in Python), or the list never ends.
An empty list (head is null) and lists with one or two nodes do not change.

How the input is shown

A list is written as an array of its values from first node to last node. For example, [2, 4, 6] is the list 2 -> 4 -> 6. Your function gets the first node, not the array. The expected output is the array the judge reads from head after your function ends.

Hint: do it in three steps. First, find the middle with a slow and a fast pointer. Second, cut the list there and reverse the second half. Third, take one node from each half in turn and link them.

Examples

Example 1

Input:: [2,4,6,8,10]
Output:: [2,10,4,8,6]

First 2, then last 10, then second 4, then second-last 8. The middle node 6 is used last.

Example 2

Input:: [11,22,33,44,55,66]
Output:: [11,66,22,55,33,44]

With an even number of nodes, the order ends with the two middle nodes: 33, then 44.

Example 3

Input:: [7,3]
Output:: [7,3]

With two nodes, the first node is first and the last node is second, so nothing changes.

Constraints

The list has 0 to 50 nodes.
1 <= val <= 99

Run checks your code against the 3 examples. Submit checks it against all 183 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.