LeetCode 23 · Linked List

Merge k Sorted Lists, explained with a picture

A dispatcher merging trains from k tracks.

HardLinked List
▶ Watch it step by step

The problem

You are given k linked lists, each sorted. Merge them all into one sorted list.

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

Picture it

Picture k sorted trains waiting on parallel tracks and one dispatcher. At each moment the dispatcher sends out the smallest front coach among all tracks. To find that smallest coach instantly, the front coaches sit in a min-heap (a priority queue). After sending one out, the next coach on that same track joins the heap.

How to recognise it

  • You have many sorted sequences and need one sorted output, or the next smallest item across all of them.
  • At every moment the next item is the smallest of the k fronts. Only the fronts matter; nothing deeper in a list can be smaller than its own front.
  • You need "give me the minimum, then replace it with another item" over and over. That is what a min-heap (a priority queue: a structure that returns its smallest item in O(log k) and accepts a new one in O(log k)) is built for.
  • k can be large (LeetCode allows 10^4 lists), so scanning all fronts for every node is expensive.

Start with brute force

Keep the current front of each list. To pick each next node, scan all fronts for the smallest, link it, and advance that list.

def merge_k_brute(lists):
    heads = [l for l in lists if l]
    dummy = tail = Node(0)
    while heads:
        best = min(range(len(heads)), key=lambda i: heads[i].val)
        tail.next = heads[best]
        tail = tail.next
        if heads[best].next:
            heads[best] = heads[best].next
        else:
            heads.pop(best)
    return dummy.next

Each of the N nodes costs a scan of up to k fronts, so time is O(N · k) and extra space O(k). LeetCode allows k = 10^4 lists and N = 10^4 nodes in total, which is up to about 10^8 comparisons. (Collecting all values and sorting them, O(N log N), is faster but builds new nodes and ignores that the lists are sorted.)

From brute force to the idea

  1. Find the waste. Each scan looks at k fronts, but only one front changed since the last scan. Everything else is compared again for nothing.
  2. Keep the fronts in a heap. Put (value, list index, node) for each non-empty list into a list and call heapify, which arranges it as a min-heap in O(k).
  3. Pop the smallest, push its successor. heappop gives the smallest front in O(log k). Link it to the tail. If that node has a next, push it: it is the new front of the same list.
  4. Why the list index is there. Python compares tuples item by item. When two values are equal it compares the second item; without the index it would compare two Node objects and raise TypeError. Each list has only one node in the heap at a time, so the index alone always breaks a tie.
  5. Stop when the heap is empty. Every node has been linked exactly once. A dummy node again avoids a special case for the first one.

This is the key idea: a min-heap of the k current fronts, so each next node costs O(log k) instead of O(k).

Merging the lists in pairs (1 with 2, 3 with 4, and so on, then again) also reaches O(N log k) without a heap.

The key idea

A min-heap of the k front nodes gives the next smallest in O(log k): total O(N log k).

Python solution

def merge_k(lists):
    heap = [(l.val, i, l) for i, l in enumerate(lists) if l]
    heapify(heap)
    dummy = tail = Node(0)
    while heap:
        val, i, node = heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heappush(heap, (node.next.val, i, node.next))
    return dummy.next

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop, heapify

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(N · k): a scan of up to k fronts for each of the N nodesO(k): the list of fronts
Min-heap (shown code)O(N log k): one pop and at most one push per node, on a heap of at most k entries, plus O(k) for heapifyO(k): the heap; nodes are relinked, not copied

Edge cases

  • No lists ([]) or only empty lists ([None, None]): the heap starts empty and the code returns None.
  • One list: its nodes come out in their original order.
  • Equal values in different lists ([1 → 4 → 5, 1 → 3 → 4, 2 → 6]): ties are broken by list index, so the 1 from list 0 comes first. The result is 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6.
  • Very uneven lengths: fine; a list leaves the heap when its last node is popped.
  • Imports: the shown code needs from heapq import heapify, heappop, heappush.

Common mistakes

  • Pushing (val, node) without a tie-breaker, which raises TypeError as soon as two fronts have equal values.
  • Pushing every node of every list at the start. It works, but the heap holds N entries, so time becomes O(N log N) and space O(N).
  • Merging the lists one after another into a growing result. Each merge re-walks the result, which costs O(N · k) in the worst case.
  • Forgetting to skip empty lists when building the heap, so l.val is read on None.
Your turn: k sorted arrays

Given k sorted Python lists of numbers, return one sorted list of all their values. For [[1, 4, 5], [1, 3, 4], [2, 6]] the answer is [1, 1, 2, 3, 4, 4, 5, 6]. Describe your approach, then write it if you like.

Compare with our answer

Same heap of fronts, but an array has no next pointer, so each heap entry also stores the position inside its array. After popping (value, i, j), push element j + 1 of array i if it exists.

from heapq import heapify, heappop, heappush

def merge_k_arrays(arrays):
    heap = [(a[0], i, 0) for i, a in enumerate(arrays) if a]
    heapify(heap)
    out = []
    while heap:
        val, i, j = heappop(heap)
        out.append(val)
        if j + 1 < len(arrays[i]):
            heappush(heap, (arrays[i][j + 1], i, j + 1))
    return out

Time O(N log k), extra space O(k) for the heap plus O(N) for the output.

A strong answer mentions: the (value, array, position) entry, skipping empty arrays, and why the heap never grows beyond k.

Check what stuck

1. A service must merge 1,000 sorted log files by timestamp into one stream, using little memory. Which approach fits best?

2. Why is the shown code O(N log k) rather than O(N log N)?

3. A learner pushes (node.val, node) tuples, without the list index. Which input raises a TypeError?

Score 60% or more and the lesson is marked complete.