Given a singly linked list, L = {n_{1}, n_{2}, …, n_{n-1}, n_{n}}, reorder it so that L = {n_{1}, n_{n}, n_{2}, n_{n-1}, …}. Rearrange the nodes not just the values. Do it in place.

Example

Input Result
1->2->3->4 1->4->2->3
1->2 1->2

The following algorithm maps the list to an array and reorders the nodes in the array. This is a simple solution. The time and space complexity is both O(n) where n is the number of nodes in the list. However, I got ‘Memory Limit Exceeded’ for this algorithm.

I got accepted for the following algorithm. The time complexity is O(n^{2}), and space complexity O(1).