List 2: 1 5 List 3: 1 1 3 7 List 4: 8 Merged Linked List: 1 1 1 2 3 4 5 6 7 8

Complexity Analysis

Time Complexity:

Everytime two lists are merged the time complexity is proportional to the sum of the number of nodes in them as we iterate over all nodes and merge according to the data values in them.

Assume the length of each list to be N1, N2, N3 and so on.

In the first iteration, when merging the first two lists (N1 and N2), the time complexity is N1 + N2.
In the second iteration, when merging the result of the first iteration with the third list (N3), the time complexity becomes (N1 + N2) + N3.
In the third iteration, merging the result of the second iteration with the fourth list (N4), the time complexity becomes ((N1 + N2) + N3) + N4.
This pattern continues until all K lists are merged.

The total time complexity can be expressed as:

T = (N1 + N2) + (N1 + N2 + N3) + .... + (N1 + N2 + N3 + .... + Nk)

For simplification let's assume the length of each linked list to be proportional to N,

T = N + 2N + 3N + 4N + 5N + .... + kN

T = N (1 + 2 + 3 + 4 + ... + k)

The sum of lengths of the lists can be calculated using the formula for the sum of the first N natural numbers:

T = N (k(k+1))/2

Hence, the time complexity is O( N*k(k+1)/2) ~ O(N*k^2)

Space Complexity: O(1) as no additional data structures or space is allocated for storing data, only a constant space for pointers to maintain for traversing the linked list and merging them in place.

Optimal Approach

Algorithm / Intuition