Merge k Sorted Lists

Hard Problem 60 of 151 Java and Python

Problem

You are given an array of k linked lists, each sorted in ascending order. Merge them into one sorted linked list and return it.

Example 1

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

Example 2

Input: lists = []
Output: []

Constraints

0 ≤ k ≤ 10⁴
0 ≤ total number of nodes ≤ 10⁴

Explanation

The next node of the result is the smallest of the k current heads. Finding a minimum among k items again and again is what a min-heap is for.

Pop the smallest head, attach it, and push that list's next node. Each node goes in and out of the heap once, costing O(log k).

Approach 1 · Naive

Collect all values and sort

Time O(N log N)
Space O(N)

Put every value in one array, sort it and build a new list.

Collect all N values.
Sort and build the list.

Java

import java.util.*;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> values = new ArrayList<>();
        for (ListNode list : lists) {
            for (ListNode n = list; n != null; n = n.next) {
                values.add(n.val);
            }
        }
        Collections.sort(values);
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

Python

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        values = []
        for node in lists:
            while node:
                values.append(node.val)
                node = node.next
        dummy = tail = ListNode()
        for v in sorted(values):
            tail.next = ListNode(v)
            tail = tail.next
        return dummy.next

Approach 2 · Optimal

Min-heap of list heads

Time O(N log k)
Space O(k)

Keep the smallest unmerged node of each list in a min-heap. Repeatedly pop the minimum, append it, and push its successor.

Push every non-empty head into a min-heap ordered by value.
While the heap is not empty: pop node, append it to the result, and push node.next if it exists.

Java

import java.util.*;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
        for (ListNode list : lists) {
            if (list != null) {
                heap.offer(list);
            }
        }
        ListNode dummy = new ListNode();
        ListNode 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;
    }
}

Python

import heapq

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # The index i breaks ties so ListNode objects are never compared.
        heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
        heapq.heapify(heap)
        dummy = tail = ListNode()
        while heap:
            _, i, node = heapq.heappop(heap)
            tail.next = tail = node
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
        return dummy.next

Complexity compared

Approach	Time	Space
Naive Collect all values and sort	O(N log N)	O(N)
Optimal Min-heap of list heads	O(N log k)	O(k)

Key takeaways

Divide and conquer (merge lists in pairs, like merge sort) is the other O(N log k) answer, with O(1) extra space.
In Python, add a tie-breaker to heap entries; nodes themselves are not comparable.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem