Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is 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] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted linked list: 1->1->2->3->4->4->5->6

Example 2:

Input: lists = [] Output: []

Example 3:

Input: lists = [[]] Output: []

Constraints:

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.

Approach: Priority Queue (Min-Heap)

Algorithm

1. Push the head of every non-empty list into a min-heap ordered by node value
2. Repeatedly pop the smallest node, append it to the result, and push its next node back into the heap
3. Continue until the heap is empty

Time & Space Complexity

• Time Complexity: O(N log k) - N total nodes, each heap operation costs O(log k)
• Space Complexity: O(k) - the heap holds at most one node per list (plus the output list)

Java Implementation

import java.util.PriorityQueue;

public class MergeKSortedLists {

    private static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * Merge k sorted linked lists into one sorted list.
     * @param lists Array of sorted linked lists
     * @return Head of the merged list
     */
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap =
                new PriorityQueue<>((a, b) -> a.val - b.val);

        for (ListNode node : lists) {
            if (node != null) {
                heap.offer(node);
            }
        }

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

        while (!heap.isEmpty()) {
            ListNode smallest = heap.poll();
            tail.next = smallest;
            tail = tail.next;
            if (smallest.next != null) {
                heap.offer(smallest.next);
            }
        }

        return dummy.next;
    }

    // Test method
    public static void main(String[] args) {
        MergeKSortedLists m = new MergeKSortedLists();

        ListNode l1 = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode l3 = new ListNode(2, new ListNode(6));

        ListNode result = m.mergeKLists(new ListNode[]{l1, l2, l3});
        System.out.print("Input: lists = [[1,4,5],[1,3,4],[2,6]]\nOutput: [");
        for (ListNode node = result; node != null; node = node.next) {
            System.out.print(node.val);
            if (node.next != null) {
                System.out.print(",");
            }
        }
        System.out.println("]"); // Expected: [1,1,2,3,4,4,5,6]

        System.out.println("Output: " + m.mergeKLists(new ListNode[]{}));
        // Expected: null
    }
}

Alternative Approach: Divide and Conquer

public ListNode mergeKListsDivideConquer(ListNode[] lists) {
    if (lists.length == 0) {
        return null;
    }
    return mergeRange(lists, 0, lists.length - 1);
}

private ListNode mergeRange(ListNode[] lists, int lo, int hi) {
    if (lo == hi) {
        return lists[lo];
    }
    int mid = lo + (hi - lo) / 2;
    ListNode left = mergeRange(lists, lo, mid);
    ListNode right = mergeRange(lists, mid + 1, hi);
    return mergeTwo(left, right);
}

private ListNode mergeTwo(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) {
            tail.next = a;
            a = a.next;
        } else {
            tail.next = b;
            b = b.next;
        }
        tail = tail.next;
    }
    tail.next = a != null ? a : b;
    return dummy.next;
}

Example Walkthrough

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

1. Heap starts with heads: 1(1st), 1(2nd), 2
2. Pop 1 -> append; push 4 from the first list
3. Pop 1 -> append; push 3 from the second list
4. Pop 2 -> append; push 6
5. Continue popping 3, 4, 4, 5, 6

Result: [1,1,2,3,4,4,5,6].

Key Points

1. Single Head Per List: Only list heads are needed in the heap; the next nodes replace them
2. Sentinel Dummy: The dummy head simplifies appending and avoids null checks
3. Comparator: The heap is ordered by node value to always yield the smallest current element
4. Divide and Conquer: Merging pairs bottom-up also achieves O(N log k) without extra heap space
5. Edge Cases: Empty arrays and arrays of empty lists are handled naturally