Sort Linked List

Moderate

0/80

Contributed by

74 upvotes

Problem statement

Given a linked list of 'N' nodes, which has nodes in alternating non-decreasing and non-increasing. Sort the list in non-decreasing order.

For Example:

If given linked list is 1->9->3->8->4 then it should be modified to 1->3->4->8->9.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer 'N', the size of the linked list.
The second line contains 'N' space-separated integers in alternating ascending and descending orders.

Output Format :

The output contains all the integers in non-decreasing order.

Note :

You are not required to print the output, it has already been taken care of. Just implement the function.

Sample Input 1 :

7
1 9 2 8 3 7 4

Sample Output 1 :

1 2 3 4 7 8 9

Explanation to Sample Input 1 :

Since the given list is 1-> 9-> 2-> 8 -> 3 -> 7-> 4.
After sorting, it will be 1-> 2-> 3-> 4-> 7-> 8-> 9.

Sample Input 2 :

6
7 15 8 14 9 13

Sample Output 2 :

7 8 9 13 14 15

Explanation to Sample Input 1 :

Since the given list is 7-> 15-> 8-> 14 -> 9 -> 13.
After sorting, it will be 7-> 8-> 9-> 13-> 14-> 15.

Expected Space Complexity:

Try to solve this problem in O(1) space complexity.

Constraints :

1 <= N <= 10^3
0 <= data <= 10^3 

Where 'N' is the length of the linked list.

Time Limit: 1 sec

Console