Merge k Sorted Lists
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
Problem
You get an array of k linked lists, each sorted ascending. Combine them into a single sorted linked list and return its head.
Examples
Constraints
- • 0 <= k <= 10^4
- • Total nodes N <= 10^4
- • Each list is sorted ascending
Hints & approach
Hint 1
Merging the lists one after another into a growing result costs O(kN).
Hint 2
Merge them in pairs, like the merge step of merge sort.
Hint 3
Alternatively, keep the current head of every list in a min-heap.
Approachtry the hints first
Divide and conquer: merge list 0 with 1, 2 with 3, and so on, halving the number of lists each round using the two-list merge. After log k rounds one list remains, and every node took part in log k merges. The min-heap alternative pushes each list's head, then repeatedly pops the smallest node, appends it, and pushes that node's successor; it has the same bound.
Time O(N log k) · Space O(1) for pairwise merging, O(k) with a heap
