Merge K Sorted Lists

Share

You are given an array of k linked lists lists, each sorted in ascending order. Merge all the linked lists 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:

Contents

Approach 1: Brute Force

Collect all values into a list, sort it, rebuild the linked list.

Java
public ListNode mergeKLists(ListNode[] lists) {
    List<Integer> values = new ArrayList<>();
    for (ListNode list : lists) {
        while (list != null) {
            values.add(list.val);
            list = list.next;
        }
    }
    Collections.sort(values);

    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    for (int v : values) {
        curr.next = new ListNode(v);
        curr = curr.next;
    }
    return dummy.next;
}
// Time: O(N log N) where N = total nodes. Space: O(N)

Approach 2: Min-Heap

Always extract the globally minimum node from the k current list heads. Use a min-heap to efficiently find the minimum among the heads.

Algorithm:
Java
public ListNode mergeKLists(ListNode[] lists) {
    // Min-heap ordered by node value
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
        Comparator.comparingInt(n -> n.val)
    );

    // Initialise heap with the head of each non-null list
    for (ListNode list : lists) {
        if (list != null) minHeap.offer(list);
    }

    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;

    while (!minHeap.isEmpty()) {
        ListNode node = minHeap.poll();  // smallest current head
        curr.next = node;
        curr = curr.next;
        if (node.next != null) {
            minHeap.offer(node.next);   // push the next node from the same list
        }
    }
    return dummy.next;
}

Complexity Analysis
ApproachTimeSpace
Brute ForceO(N log N)O(N)
Min-HeapO(N log k)O(k): heap holds at most k nodes

Note: N = total number of nodes across all lists, k = number of lists.