Flattening of Linked List Python

If we are given a linked list with each node being a separate linked list and two pointers of the same type:

1. One pointer points towards the next node of the primary linked list (referred to as the 'prim' pointer in the program below).
2. One pointer points towards the next node of the secondary linked list (the 'sec' pointer in the program below).

Every linked list, primary and secondary, should be sorted, and the resulting linked list, which will be a flat linked list, should also be sorted.

Examples

Input:

Output:

6 -> 7 -> 9 -> 15 -> 21 -> 25 -> 26 -> 29 -> 30 -> 30 -> 31 -> 51 -> 56

Input:

Output:

4 -> 5 -> 8 -> 9 -> 10 -> 15 -> 15 -> 17 -> 21 -> 30 

The strategy is to define a function to merge the linked lists. We will merge the lists sequentially using the merge() function, recursively merging the current linked list to the recently flattened list. We will use the sec pointer to connect flattened list nodes.

The algorithm of the problem is as follows:

• We will recursively merge the current iteration's linked list to the subsequent linked list.
• If the linked list of the current iteration does not have any nodes, i.e., it is empty, or the next linked list is None, the linked list of the current iteration is returned. This condition will serve as the base condition.
• We will begin combining the linked lists with the most recent ones.
• We will return the head of the linked list of the current iteration after merging the present and the previously flattened linked list.

The mentioned technique is implemented as follows:

Code

Output:

The flattened linked list is: 
6 7 9 15 21 25 26 29 30 30 31 51 56 

Time Complexity: The time complexity of this program is O(n * n * m). Here N is the total number of nodes in the primary linked list, and M represents the number of nodes of a single sub-linked list

Auxiliary Space: O(n * m).

Since we are merging two linked lists simultaneously,

• When we add the first two sub-linked lists, the time complexity will be O(m + m) = O(2m).
• In the next step, we will merge one more sub-linked list to the new merged linked list. Therefore, the time complexity will be O(2m + m) = O(3M).
• In the next step, we will merge one more list. Therefore the time complexity will be O(3m + m).
• In this way, we will continue merging the sub-linked lists to the already merged linked list.
• This step will be repeated n number of times; therefore this approach will take a total time of O(2m + 3m + 4m + …. n * m) = (2 + 3 + 4 + … + n)*m
• Further solving the above equation: time complexity = O((n * n + n - 2) * m / 2)
• The approximation of the above equation will lead to O(n * n * m) for a large value of n

Since we are using a recursive approach, the space complexity of this approach is O(n * m). The recursive function used in this approach will create a recursive stack. The size of this stack will be equivalent to the total number of nodes present in the given nested linked list, which is n * m.

Flattening a Linked List using Priority Queues

The approach is to create a Min-Heap and place the head node of each linked list into this data structure. Then, using the Extract-min method, obtain the minimum integer from the priority queue and proceed in the linked list using that minimum element.

To implement this strategy, we will use the following algorithm:

• The head node of each linked list is pushed into the Min-heap priority queue.
• Then we will extract the minimum integer value node out of the priority queue while it is not empty, and if the next node points towards the minimum value node, then we will push that node into the priority queue.
• Additionally, after extracting the minimum value node, we will print the node's value each time.

We will implement this algorithm in Python as follows.

Code

Output:

30 9 7 6 51 26 21 56 31 30 29 

Time Complexity: The time complexity of this approach is O(N * M * log(N)). Here N is the number of nodes in the main or primary linked list, and M represents the number of nodes in a single sub-linked list.

Auxiliary Space: The space complexity of this approach is O(N). Here N is the number of nodes present in the main linked list.