# Rearrange the linked list so that it has alternating high, low values

Given an linked list of integers, rearrange it such that every second node of the linked list is greater than its left and right nodes. In other words, rearrange linked list node in alternating high-low.

Assume no duplicate nodes are present in the linked list. Several lists might satisfies the constraints, we need to print any one of them. For example,

Input:  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
Output: 1 -> 3 -> 2 -> 5 -> 4 -> 7 -> 6

Input:  9 -> 6 -> 8 -> 3 -> 7
Output: 6 -> 9 -> 3 -> 8 -> 7

Input:  6 -> 9 -> 2 -> 5 -> 1 -> 4
Output: 6 -> 9 -> 2 -> 5 -> 1 -> 4

The idea is to start from the second node in the linked list and advance two nodes at a time for each iteration of loop. If previous node is greater than the current node, we swap their values. Similarly, if next node is greater than the current node, we swap both values. At the end of loop, we will get the desired linked list that satisfies given constraints.

## C

Output:

1 -> 3 -> 2 -> 5 -> 4 -> 7 -> 6 -> 8 -> 6 -> null

## Java

Output:

1 -> 3 -> 2 -> 5 -> 4 -> 7 -> 6 -> 8 -> 6 -> null

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

(1 votes, average: 5.00 out of 5)