Coding interview problems › Heaps & Top-K

🔺 Heaps & Top-K Hard

Merge K Sorted Lists

Merge K Sorted Lists: a min-heap of the k current heads always yields the next smallest node, O(N log k). Tested Python, pitfalls and a live heap visual.

Also searched as: merge k sorted linked lists · merge k sorted arrays using heap · k-way merge

🔺

Try it live Free

Binary Heap & Priority Queue

Use the heap lab to watch pop-min take the root and sift down; in this problem each pop hands you the next node of the merged list.

Also useful: Linked Lists: Reverse & Floyd's Cycle

Open the playground →

The problem

You are given k linked lists, each sorted in ascending order. Merge them into one sorted linked list and return its head.

Input[1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6]
Output1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
Input[]
Outputempty list

The key insight

The next node of the answer is always the smallest of the k current heads. A min-heap holding one head per list gives you that smallest head in O(log k). Pop it, attach it to the result, and push its successor from the same list.

Brute force first: Merging the lists one after another into a growing result costs O(N·k) for N total nodes, because early nodes get re-scanned on every merge.

Step-by-step approach

  1. Push (node.val, i, node) for the head of every non-empty list; i breaks ties so nodes are never compared.
  2. Create a dummy node and a tail pointer.
  3. While the heap is not empty, pop the smallest entry and attach its node to tail.
  4. If that node has a next, push it with the same list index.
  5. Return dummy.next.

Python solution

PYTHON 3tested
import heapq


class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next


def merge_k_lists(lists):
    heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
    heapq.heapify(heap)
    dummy = tail = ListNode()
    while heap:
        val, i, node = heapq.heappop(heap)  # smallest current head
        tail.next = tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    tail.next = None
    return dummy.next

Complexity

TimeO(N log k)
SpaceO(k)

Each of the N nodes is pushed and popped once on a heap that never holds more than k entries, so each operation is O(log k).

Common mistakes

Frequently asked questions

What is the time and space complexity of merging k sorted lists?

O(N log k) time for N total nodes, and O(k) extra space for the heap.

Is there a solution without a heap?

Divide and conquer: merge the lists in pairs, then merge the results in pairs, and so on. There are log k rounds of O(N) work, which is also O(N log k).

Why include the list index in the heap tuple?

Heap entries are compared element by element. When two node values tie, the index decides the order, so Python never has to compare two ListNode objects.

Does this work for sorted arrays instead of linked lists?

Yes. Store (value, list index, position) in the heap and push the next position of the same array after each pop. heapq.merge does this lazily for iterables.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Heaps & Top-K Binary Heap & Priority Queue lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.