101. Merge K Sorted Linked Lists

Given k sorted singly linked lists (each given as its length followed by its sorted values), merge all of them into a single sorted list and print it.

Input: The first line contains an integer k, the number of lists. Then for each of the k lists: a line with that list's length, followed by a line of that many space-separated sorted integers. Output: Print the fully merged, sorted sequence of every list's values, space-separated, on one line.

1 <= k <= 100, 1 <= each list's length <= 1000

This is the direct k-way generalization of 'Merge Two Sorted Linked Lists' - recognizing that a min-heap replaces the simple two-pointer comparison when there are MORE than two sources to merge from is the key generalization insight.

Given k sorted linked lists, merge all of them into one single fully sorted linked list. Brute force: Concatenate all k lists' values into one big list and sort it with a general-purpose algorithm - this costs O(N log N) where N is the total element count, ignoring that each individual list is ALREADY sorted. Optimised: A min-heap holding just one candidate node per list lets you always find the next-smallest value across ALL k lists in O(log k) - since each list is already internally sorted, this extends the two-list merge technique to k lists efficiently, without ever needing to fully sort anything from scratch.

Walk through all k lists, dump every value into one big array, and sort that array with a standard comparison sort, then rebuild a linked list from the sorted array. This is correct because sorting the union of all values naturally produces the fully merged sorted sequence, but it completely ignores the fact that each individual list is already sorted, doing far more comparison work than necessary. Time: O(N log N), where N is the total number of nodes Space: O(N)

Push the head node of each of the k lists into a min-heap keyed by value. Repeatedly pop the smallest node from the heap, append it to the result list, and if that node had a 'next' node in its original list, push that next node into the heap. This always advances the globally smallest available element next, achieving the same result as the pairwise merges but touching each of the N nodes only once with an O(log k) heap operation, instead of repeatedly re-scanning a growing merged list. Time: O(N log k) Space: O(k)

Merge the first two lists together using the standard two-pointer merge-two-sorted-lists technique, then merge that result with the third list, then with the fourth, and so on until all k lists have been folded into one. Each individual merge step is efficient and takes advantage of both inputs already being sorted, but because the partially-merged list keeps growing, later merges each re-scan an increasingly large combined list, so the total work across all k-1 merges is higher than necessary. Time: O(N * k) Space: O(1) extra, beyond the output list

1. Seed a min-heap with the current front NODE of each of the k lists. 2. Repeatedly pop the smallest, relink it onto the result, and push that same list's NEXT node (if any) back into the heap. 3. Continue until every list has been fully exhausted.

Time: O(N log k), where N is the total number of nodes across all k lists - each node triggers one O(log k) heap operation. Space: O(k), for the heap holding at most one candidate node per list at any time.

k = 1 (only one already-sorted list to merge); a list at the minimum length 1 and one at the maximum length 1000; duplicate values across different lists, as in the example (1 appears in two lists).

Be ready to mention the alternative 'merge pairs of lists repeatedly' approach (like a tournament bracket, merging two at a time until one list remains) as another valid O(N log k) technique, without needing an explicit heap.