Sort in odd increasing even decreasing linked list

In the given linked list, odd numbered nodes are in increasing order and even numbered nodes are in decreasing order. How it can be sorted in increasing order?

Solution is very easy and is in linear time.

Given linked list

a1->a2->a3->......an

a1, a3, a5... are in increasing order.
a2, a4, a6... are in decreasing order.

First step is to get the linked list of odd numbered nodes only.
Means a1->a3->a5->...
This can be done in O(n)

Similar for even numbered nodes, a2->a4->.... This is again in linear time.
Now reverse the a2->a4-> list. It can be done in O(n).

Merge it with a1->a3->... It also has linear complexity.

And you will get a sorted linked list in linear time.