How do you approach Merge k Sorted Lists?

Use a min-heap to efficiently get the smallest element among all lists.

What is the time complexity of Merge k Sorted Lists?

Time complexity: O(N log k) where N is total elements. Space complexity: O(k) for heap.

What are common mistakes on Merge k Sorted Lists?

Reassigning next before saving it, which loses the rest of the list. Skipping the dummy head, which forces a special case every time the real head changes. Advancing the fast pointer without checking both fast and fast.next - the null dereference only shows up on even-length lists.

gitGood.dev

← Back to problems

Merge k Sorted Lists

HardData Structures

Description

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Note: For this problem, linked lists are represented as arrays for simplicity.

Example 1

Input: lists = [[1,4,5],[1,3,4],[2,6]]

Output: [1,1,2,3,4,4,5,6]

Example 2

Input: lists = []

Output: []

Example 3

Input: lists = [[]]

Output: []

Constraints

- k == lists.length - 0 <= k <= 10^4 - 0 <= lists[i].length <= 500 - -10^4 <= lists[i][j] <= 10^4 - lists[i] is sorted in ascending order. - The sum of lists[i].length will not exceed 10^4.

Merge k Sorted Lists: approach, complexity and pitfalls

A hard linked list problem, graded against 6 test cases (3 of them hidden).

The pattern: Linked List

Pointer manipulation - reversal, cycle detection, and merging without extra space.

Reach for it when you see: Any problem handing you a list head, especially with an O(1) space constraint.

If you are stuck

Show the 3-step hint ladder

Use a min-heap to efficiently get the smallest element among all lists.
Alternatively, use divide and conquer to merge pairs of lists.
Keep track of which list each element came from.

The optimal approach

Show the approach: Solution 1: Min-Heap

Use a heap to always pick the smallest element from all k lists.

Solution 2: Divide and Conquer

Merge lists in pairs until only one remains.

Time: O(N log k) where N is total elements
Space: O(k) for heap

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Linked List mistakes

These apply to the pattern as a whole, not just this problem.

Reassigning `next` before saving it, which loses the rest of the list.
Skipping the dummy head, which forces a special case every time the real head changes.
Advancing the fast pointer without checking both `fast` and `fast.next` - the null dereference only shows up on even-length lists.

← Back to problems

Merge k Sorted Lists

HardData Structures

Description

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Note: For this problem, linked lists are represented as arrays for simplicity.

Example 1

Input: lists = [[1,4,5],[1,3,4],[2,6]]

Output: [1,1,2,3,4,4,5,6]

Example 2

Input: lists = []

Output: []

Example 3

Input: lists = [[]]

Output: []

Constraints

- k == lists.length - 0 <= k <= 10^4 - 0 <= lists[i].length <= 500 - -10^4 <= lists[i][j] <= 10^4 - lists[i] is sorted in ascending order. - The sum of lists[i].length will not exceed 10^4.

Merge k Sorted Lists: approach, complexity and pitfalls

A hard linked list problem, graded against 6 test cases (3 of them hidden).

The pattern: Linked List

Pointer manipulation - reversal, cycle detection, and merging without extra space.

Reach for it when you see: Any problem handing you a list head, especially with an O(1) space constraint.

If you are stuck

Show the 3-step hint ladder

Use a min-heap to efficiently get the smallest element among all lists.
Alternatively, use divide and conquer to merge pairs of lists.
Keep track of which list each element came from.

The optimal approach

Show the approach: Solution 1: Min-Heap

Use a heap to always pick the smallest element from all k lists.

Solution 2: Divide and Conquer

Merge lists in pairs until only one remains.

Time: O(N log k) where N is total elements
Space: O(k) for heap

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Linked List mistakes

These apply to the pattern as a whole, not just this problem.

Reassigning `next` before saving it, which loses the rest of the list.
Skipping the dummy head, which forces a special case every time the real head changes.
Advancing the fast pointer without checking both `fast` and `fast.next` - the null dereference only shows up on even-length lists.