Merge k Sorted Lists

hardLinked List59 stepsJava · Python · C++

Merge k sorted lists into one. Put the head of every list in a min-heap keyed by value. Repeatedly pop the smallest node, attach it to the result, and push its successor.

▶ Watch the animated trace

Traced input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]] → [1, 1, 2, 3, 4, 4, 5, 6]. Original problem: neetcode.io/problems/merge-k-sorted-linked-lists

Complexity

BestO(N log k)

AverageO(N log k)

WorstO(N log k)

SpaceO(k)

N total nodes; the heap never holds more than k nodes.

Key idea

The next node of the answer is always one of the k current heads.
A min-heap returns the smallest head in O(log k).
After taking a node, its next becomes that list's new head.

Common mistakes

Pushing null heads into the heap throws an exception.
Merging lists one by one is O(N·k).
Divide and conquer (pairwise merging) is the other O(N log k) solution.

Solution

Java

ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((x, y) -> Integer.compare(x.val, y.val));
    for (ListNode l : lists) if (l != null) pq.offer(l);
    ListNode dummy = new ListNode(0), tail = dummy;
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        tail.next = node;
        tail = node;
        if (node.next != null) pq.offer(node.next);
    }
    return dummy.next;
}

Python

def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    heap = [(l.val, i, l) for i, l in enumerate(lists) if l]
    heapq.heapify(heap)
    dummy = tail = ListNode(0)
    while heap:
        _, 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

C++

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
    for (ListNode* l : lists) if (l) pq.push(l);
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (!pq.empty()) {
        ListNode* node = pq.top(); pq.pop();
        tail->next = node;
        tail = node;
        if (node->next) pq.push(node->next);
    }
    return dummy.next;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
No lists The heap starts empty.	`lists = []`	`[]`
Only empty lists Null heads are skipped.	`lists = [[], []]`	`[]`
One list Nodes come out in their original order.	`lists = [[1, 2]]`	`[1, 2]`