How to 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:
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 –
Output:

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


Learn More :