# Flatten a linked list

Given a linked list which can grow in both horizontal and vertical directions (right and down), flatten it into a sorted singly linked list provided that each horizontal and vertical list is already sorted.

The given linked list is similar to the standard linked list except that it has one extra field down which points to a vertical list. Assume that the vertical list doesn’t have any horizontal list attached to it.

For example, consider below list It should be converted to below list:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> NULL

We can divide this problem into two parts:

1. Flattening: In this step, we flatten the entire list either horizontally using the next pointers or vertically using the down pointers.

2. Sorting: In this step, we sort the flattened list using the merge sort algorithm.

This is demonstrated below in C/Java:

## C

Output:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> NULL

## Java

Output:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> null

The time complexity of above solution is O(nlog(n)) where n is the number of nodes in the linked list and auxiliary space required is O(n) for merge sort algorithm.

Above solution first flattens the list, and then sort it. We can combine both these steps into one single step i.e. sorting the list while flattening the list. This can be done by calling `SortedMerge()` routine of merge sort algorithm as demonstrated below in C/Java –

## C

Output:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> NULL

## Java

Output:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> null     (2 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂  