Flattening a Linked List

Problem Statement

Given a Linked List of size N, where every node of the linked list has either of the two pointer or can have both pointer.

1. Pointer to the next node - next pointer
2. bottom pointer to a sub-linked list - bottom pointer

The sublinked(vertical linked list) and the horizontal linked list is in sorted order. Flatten this linked list such that all the nodes appear in a single level(horizontally) and the node elements are in sorted order.

Example

number of nodes in the horizontal linked list(head nodes) = $4$

Array of number of nodes in every sublinked list to the bottom including head node = $[4,2,1,3]$

After flatteneing the linked list, the linked list should look like :

The elements of the flattened linked list are :

$[4,6,7,8,9,10,12,13,20,30]$

Example Explanation

In the example below lets understand the initial structure of linked list and the final structure after merging of linked list.

In the above linked list diagram we can see there is a single horizontal linked list and some vertical sub-linked list connected to the bottom pointer of the nodes of horizontal linked list.

The node of the horizontal linked list (4->6->8->10) have two pointer. One pointer(next pointer) points to the next node in the horizontal linked list itself and the second pointer (bottom pointer) points to the vertical sublinked list atted to each node of the horizontal linked list.

The bottom pointer of node with data = 4 is pointing to 7->9->12 (vertical sub linked list). The vertical sublinked list is in sorted order.

The bottom pointer of node with data = 6 is pointing to 13. (vertical sublinked list).The vertical sublinked list is in sorted order.

The bottom pointer of node with data = 8 points to NULL, which means there is no vertical sublinked list underneath node with data = 8.The vertical sublinked list is in sorted order.

The bottom pointer of node with data = 10 points to 20->30 . (vertical sublinked list).The vertical sublinked list is in sorted order.

When all the elemnts of the horizontal and vertical sub-linked list are merged to a single linked list . The linked then looks like :

All the elements in the above flattened Linked list lt is in sorted order. Flattening of the linked list can be done by two methods which are explained further in this article.

Approach 1 : Merging in Merge Sort Algorithm

As each sub-list in the linked list is in sorted order we can use merge sort on the sub list to merge all the sublist to a single list.

The steps used in this algorithm are :

1. create a dummy node with two pointer. one pointer is used to keep track of the dummy node and the second pointer is used to move ahaed as we merge the linked list.
2. Choose any two sub-linked list and iterate through the list and merge them using merge algorithm of merge sort.
3. Return the final list after all sub-list are merged to a single list.

Implementation in C++

Implementation in Java :

Implementation in python :

Output of the code :

Time complexity :

• If we consider each vertical linked list of size O(M) in the worst case, then in this method we are merging two vertical sub-linked list at a time.
• Time taken to merge two linked list of size M = $O(M+M) =O(2M)$
• Similarly, time taken to merge another linked list of size M with linked list of size 2M = $O(M+2M)=O(3M)$
• Similarly, time taken to merge another linked list of size M with linked list of size $3M = O(M+3M) =O(4M)$.
• This process will take place N times where N is the no of nodes in the horizontal linked list. So, the total time taken till all the nodes are merged = $O(2M+3M+4M+5M+...N * M )$ $= O(2+3+4+5+6...+N)* M$ $=O(N* ( N + 1 ) / 2)* M$ $= O(N * N * M)$

Space Complexity :

• As recursion is taking place in this algorithm and the size of the recursive stack will be $O(N*M)$ where, $(N*M)$ is the total no of elements in the flattend list. So, the space complexity will be O(N*M)

Approach 2 : Using Priority Queue

We can build min-heap from the element of the linked list and extract min element from the min heap by using Extractmin property of min heap.

The steps involved in this Priority queue method are :

1. All the nodes are pushed to priority queue using next pointer untill we encounter NULL.
2. The minimum element from the queue is extracted using ExtractMin property and if the bottom pointer of that element is not pointing to any NULL value then push the element pointed by bottom pointer to the priority queue.
3. Else the element found by ExtractMin operation is printed and the size of the priority queue decreases.

Implementation in C++

Implementation in Java :

Implementation in python :

Output of the min heap code :

Time complexity :

Total no of elements present in the min heap is equal to the total number of nodes in the linked list = N * M. where N is the number of nodes in horizontal linked list and M is the size of each verical sub-linked list in worst case. So, time taken to extract one min element from the $min heap = O(log N)$. So, time taken to extract all N*M elements from the $min heap = O(N * M * logN)$

Space complexity :

The space required to store the elements of horizontal linked list in the priority $queue = O(N)$. So, the space required is $O(N)$.