Flatten linked list implementation C

Flatten linked list

Consider a multi layered linked list which has two pointers, next and down pointer.  Node is connected to horizontal next node using next pointer and there is vertical linked list using down pointer. Now, problem is to combine all linked lists using down pointer into one. This process called flatten linked list. Example of linked list as shown in figure.

Flatten linked list

Question is to flatten such given linked list into one flat linked list. There are some constraints :

1. Only node at the top are connected using next pointers, i.e head of each node is connected to head of next list and so on.
2. All individual linked lists following down pointer are sorted in order
3. Finally flatten linked list should be in sorted order. So for above example, final output linked list should be:

flatten linked list example

Method to flatten linked list

Instead of solving the entire problem, we will start small. How about flattening one list? No work required there. Then take two lists and try flattening them. If we start from the end of multi-layered linked list, take last two lists, flatten and merge two last linked lists. How to merge two linked list : refer :  Merge two sorted linked list. This merge operation on two linked lists return a single list. Now, merge third last list with merged list returned by merging two linked lists previously. Repeat this merge till all sublists of original linked list are merged into one.

Two hints lead us to recursive nature of solution. First, problem is divided into smaller subproblems. These subproblems are then solved and literally merged to get solution of bigger problem. Second, same processing done on two lists (merge), only difference is lists change in each merge.

Flatten linked list implementation

Complexity of algorithm to flatten linked list is O(n log n) where n is total number of nodes across all sublists.

Please share your suggestion or write if something is wrong. Sharing is caring. If you want to contribute to website, please contact us.