Merge k Sorted Lists

HardK-Way MergeBlind 75SeniorOpen on LeetCodeUpdated Sep 21, 2026

You're given an array lists of k singly linked lists, each already sorted in ascending order. Merge all of their nodes into one list sorted in ascending order and return its head. Equal values may come from different lists, and their relative order doesn't matter. The array may be empty and any individual list may be empty; if there are no nodes at all, return an empty list (null).

Examples

lists = [[1,4,5],[1,3,4],[2,6]] returns [1,1,2,3,4,4,5,6]

list 0

list 1

list 2

output

The merged list takes the smallest remaining front value each time: 1 and 1 from lists 0 and 1, 2 from list 2, then 3, 4, 4, 5 and finally 6.

lists = [] returns []

There are no lists, so there are no nodes and the result is empty.

lists = [[]] returns []

The array holds one list, but that list has no nodes, so the result is still empty.

Constraints

k == lists.length
0 <= k <= 10^4
Total nodes <= 10^4

Hints

Hint 1

At any moment you only need the smallest current head among the k lists, how do you query that efficiently?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Put the head of every non-empty list into a min-heap keyed by node value. Repeatedly pop the smallest node, link it onto the result, and push that node's successor from the same list. The heap always holds the current front of every unfinished list, so each pop is the smallest node left overall. The list index rides along as a tiebreaker so Python never has to compare two nodes. O(N log k) time, O(k) space, N = total number of nodes.

Time

O(N log k)

Space

O(k)

Pitfall

In Python, pushing (val, node) tuples crashes as soon as two values tie, because heapq falls back to comparing ListNode objects. Put a tiebreaker such as the list index between the value and the node.

Solutions

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode head : lists) {
            if (head != null) heap.offer(head);
        }
        ListNode dummy = new ListNode(0), tail = dummy;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();
            tail.next = node;
            tail = node;
            if (node.next != null) heap.offer(node.next);
        }
        return dummy.next;
    }
}

import heapq

class Solution:
    def mergeKLists(self, lists):
        heap = []
        for i, head in enumerate(lists):
            if head:
                heapq.heappush(heap, (head.val, i, head))
        dummy = ListNode(0)
        tail = dummy
        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