hardDSA

How do you merge k sorted lists?

Q: How do you merge k sorted lists?

**Intuition.** At every step the next smallest element is the minimum of the current heads of all k lists. A **min-heap** holding those heads gives you that minimum in O(log k); pop it, append it to the result, and push its successor. Repeat until the heap drains. heap of k heads → pop min, push its successor 1→4→5 1→3→4 2→6 <rect x="150" y="35" width="120" height="90" rx="10" fill="#22c55e" fill-opaci

1.1k views

Understand the problem

Explain merging k sorted lists.

heaplinked-list

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Min-heap of list heads

Run Playground

import heapq

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

def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))   # i breaks ties
    dummy = tail = ListNode(0)
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next


# --- demo ---
def build(vals):
    head = None
    for v in reversed(vals): head = ListNode(v, head)
    return head
def to_list(head):
    out = []
    while head: out.append(head.val); head = head.next
    return out

merged = merge_k_lists([build([1, 4, 5]), build([1, 3, 4]), build([2, 6])])
print(to_list(merged))   # [1, 1, 2, 3, 4, 4, 5, 6]

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you design an LRU cache?

How do you detect a cycle in a directed graph?