# Rearrange linked list in specific manner in linear time

Given a linked list, rearrange linked list nodes in specific way in linear time and constant space. The alternate positions in the output list should be filled with the nodes starting from the beginning and from the very end of the original list respectively.

For example,

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

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

We can easily solve this problem by dividing it into three subproblems –

• Divide the list into two equal parts.

• Reverse the second half.

• Merge second half into first half at alternate positions. Use of extra space is not allowed (Not allowed to create additional nodes), i.e., insertion must be done in-place.

## C

Output:

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

## Java

Output:

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

The time complexity of above solution is O(n).     (1 votes, average: 5.00 out of 5) Loading... 