Search
⌘K
PricingBecome a Coach
Search
⌘K
Get Premium
Heap

Merge K Sorted Lists

hard
DESCRIPTION (inspired by Leetcode.com)

Given k linked lists, each sorted in ascending order, in a list lists, write a function to merge the input lists into one sorted linked list.

Example 1:

Inputs:

lists = [[3,4,6],[2,3,5],[-1,6]]
3 -> 4 -> 6
2 -> 3 -> 5
-1 -> 6

Output:

[-1,2,3,3,4,5,6,6]

-1 -> 2 -> 3 -> 3 -> 4 -> 5 -> 6 -> 6

Explanation

This problem can be solved using a min-heap of size k.
The min-heap will always store the next unmerged element from each of the k sorted arrays. The element with the smallest value sits at the root of the heap. We build the merged array by repeatedly popping the root from the heap. Each time we pop from the heap, we also push the next element from the same array (if one exists) onto the heap.
When the heap is empty, all elements from all arrays have been merged, and we can return the merged result.

Step 1: Initialize the heap

The first step is to initialize the heap with the first element from each of the k arrays. We iterate over each array and push a tuple containing three values onto the heap:
  • The element's value
  • The array's index (which array it came from)
  • The element's index within that array (starting at 0)
Visualization
from heapq import heappush, heappop
def mergeKLists(lists):
  if not lists:
    return None
  
  non_empty = [head for head in lists if head]
  if not non_empty:
    return None
  
  heap = []
  for head in non_empty:
    heappush(heap, (head.val, id(head), head))
  
  dummy = ListNode(0)
  current = dummy
  
  while heap:
    val, _, node = heappop(heap)
    current.next = node
    current = current.next
    
    if node.next:
      heappush(heap, (node.next.val, id(node.next), node.next))
  
  return dummy.next
346235-16

initialize heap

0 / 3

Step 2: Build the merged array

With the heap initialized, we can now build the merged result array. We start by creating an empty result array where we'll append elements in sorted order.
Visualization
from heapq import heappush, heappop
def mergeKLists(lists):
  if not lists:
    return None
  
  non_empty = [head for head in lists if head]
  if not non_empty:
    return None
  
  heap = []
  for head in non_empty:
    heappush(heap, (head.val, id(head), head))
  
  dummy = ListNode(0)
  current = dummy
  
  while heap:
    val, _, node = heappop(heap)
    current.next = node
    current = current.next
    
    if node.next:
      heappush(heap, (node.next.val, id(node.next), node.next))
  
  return dummy.next
346235-16-1,2,03,0,02,1,0

add -1 to heap

0 / 1

Now, we repeatedly pop the root of the heap, which gives us the element with the smallest value among the unmerged elements from the k arrays. We append this value to our result array.
Visualization
from heapq import heappush, heappop
def mergeKLists(lists):
  if not lists:
    return None
  
  non_empty = [head for head in lists if head]
  if not non_empty:
    return None
  
  heap = []
  for head in non_empty:
    heappush(heap, (head.val, id(head), head))
  
  dummy = ListNode(0)
  current = dummy
  
  while heap:
    val, _, node = heappop(heap)
    current.next = node
    current = current.next
    
    if node.next:
      heappush(heap, (node.next.val, id(node.next), node.next))
  
  return dummy.next
346235-16-1,2,03,0,02,1,00curr

initialize result array

0 / 1

To ensure that our heap always contains the next unmerged element from each array, after popping an element, we check if there's a next element in the same array. If there is, we push a tuple with the next element's value, the same array index, and the incremented element index onto the heap.
Visualization
from heapq import heappush, heappop
def mergeKLists(lists):
  if not lists:
    return None
  
  non_empty = [head for head in lists if head]
  if not non_empty:
    return None
  
  heap = []
  for head in non_empty:
    heappush(heap, (head.val, id(head), head))
  
  dummy = ListNode(0)
  current = dummy
  
  while heap:
    val, _, node = heappop(heap)
    current.next = node
    current = current.next
    
    if node.next:
      heappush(heap, (node.next.val, id(node.next), node.next))
  
  return dummy.next
346235-162,1,03,0,00-1curr

add -1 to result

0 / 1

When the heap is empty, all elements from all arrays have been merged, and we can return the result array.
Visualization
from heapq import heappush, heappop
def mergeKLists(lists):
  if not lists:
    return None
  
  non_empty = [head for head in lists if head]
  if not non_empty:
    return None
  
  heap = []
  for head in non_empty:
    heappush(heap, (head.val, id(head), head))
  
  dummy = ListNode(0)
  current = dummy
  
  while heap:
    val, _, node = heappop(heap)
    current.next = node
    current = current.next
    
    if node.next:
      heappush(heap, (node.next.val, id(node.next), node.next))
  
  return dummy.next
346235-160-12334566curr

add 6 to result

0 / 1

Solution

|
list of integers
Try these examples:
Visualization
from heapq import heappush, heappop
def mergeKLists(lists):
  if not lists:
    return None
  
  non_empty = [head for head in lists if head]
  if not non_empty:
    return None
  
  heap = []
  for head in non_empty:
    heappush(heap, (head.val, id(head), head))
  
  dummy = ListNode(0)
  current = dummy
  
  while heap:
    val, _, node = heappop(heap)
    current.next = node
    current = current.next
    
    if node.next:
      heappush(heap, (node.next.val, id(node.next), node.next))
  
  return dummy.next
346235-16

merge k sorted arrays

0 / 19

Test Your Knowledge

Login to take the complexity quiz and track your progress

Complexity Analysis

Time Complexity: O(n * log k) where n is the total number of elements across all input arrays and k is the number of arrays. We iterate over all elements from all arrays. At each iteration, we push and pop elements from the heap, which takes O(log k) time.

Space Complexity: O(k) where k is the number of arrays. We use a min-heap of size k to store the next unmerged element from each of the k arrays.

Mark as read

Next: Find Median from Data Stream

Your account is free and you can post anonymously if you choose.

Unlock Premium Coding Content

Interactive algorithm visualizations
Guided Practice
Recent interview questions
Learn More
Reading Progress

On This Page

Explanation

Solution

Questions
Meta SWE Interview QuestionsAmazon SWE Interview QuestionsGoogle SWE Interview QuestionsOpenAI SWE Interview QuestionsEngineering Manager (EM) Interview Questions
Learn
Learn System DesignLearn DSALearn BehavioralLearn ML System DesignLearn Low Level DesignGuided Practice
Links
FAQPricingGift Mock InterviewsGift PremiumBecome a CoachOur CoachesHello Interview Premium
Legal
Terms and ConditionsPrivacy Policy
Contact
About UsProduct Support

7511 Greenwood Ave North Unit #4238 Seattle WA 98103

© 2026 Optick Labs Inc. All rights reserved.