Linked List · 068Hard
Merge k Sorted Lists
You are given an array of k linked lists, each sorted ascending. Merge them into one sorted linked list and return its head.
Constraints
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= Node.val <= 10^4
- The total node count will not exceed 10^4.
- INPUT FORMAT
- `head` is a ListNode object, not an array. The arrays in EXAMPLES list the node values in
- order; the test runner links them into real nodes before calling your function.
Examples
mergeKLists([1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6]) -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 mergeKLists([]) -> null mergeKLists([null]) -> null mergeKLists([1 -> 2 -> 3]) -> 1 -> 2 -> 3 // a single list, as-is mergeKLists([null, null, null]) -> null // every list empty mergeKLists([-2 -> 0, -1, null]) -> -2 -> -1 -> 0 // negatives, one empty
Edge cases
- An empty array of lists, or lists that are themselves empty.
- A single list is returned as-is.
Show the target complexity (spoiler)
- Naive
- O(k * N) time — repeatedly merge the next list into a running result, rescanning the
- Target
- O(N log k) time — merge pairs of lists divide-and-conquer style, or pull from a size-k min-heap of list heads.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/06-linked-list/068-merge-k-sorted-lists.js ./practice c 068