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

Flatten linked 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

Download   Run Code

Output:

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

Java

Download   Run Code

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

Download   Run Code

Output:

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

Java

Download   Run Code

Output:

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

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 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Anshul
Guest

beautifully done!