Skip to main content

23. Merge k Sorted Lists

hard

Merge k sorted linked lists into one sorted list. A staple FAANG hard problem that tests heap intuition and the divide-and-conquer alternative — interviewers often ask for both.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

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.

Examples

Example 1

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

Explanation: The linked-lists are: [1->4->5, 1->3->4, 2->6]. Merging them into one sorted list: 1->1->2->3->4->4->5->6.

Example 2

Input
lists = []
Output
[]

Example 3

Input
lists = [[]]
Output
[]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Naive 'collect everything, sort once' works but throws away the structure you were given.

Hint 2

At any point, the smallest remaining value lives at the head of one of the k lists. That's a heap.

Hint 3

Push the head of each list into a min-heap. Pop the smallest, append it to the output, push its next (if any) back in.

Hint 4

Alternative: pairwise-merge in rounds. Merge list[0] with list[1], list[2] with list[3], etc. log(k) rounds, each O(n) — same total work as the heap.

Solution approach

Reveal approach

Min-heap approach: push the head node of each non-null list into a heap, ordered by node value. Repeatedly pop the smallest, append it to a tail pointer of the result, and push its next node (if any) back into the heap. Stop when the heap is empty. O(N log k) time where N is the total number of nodes, O(k) space. The divide-and-conquer alternative pairwise-merges lists in log k rounds — same O(N log k) bound but no heap data structure. Mention both; the interviewer wants to see you choose. Edge cases to call out: empty list array, single empty list inside, all lists empty.

Complexity

Time
O(N log k)
Space
O(k)

Related patterns

  • heap
  • divide-and-conquer
  • linked-list
  • k-way-merge

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Google
  • Microsoft
  • Apple
  • LinkedIn

Practice these live with InterviewChamp.AI

Drill Merge k Sorted Lists and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →