hardLinked List

Merge k Sorted Lists

Merge k sorted linked lists into one nondecreasing list.

LeetCode ↗

Work through the cases

3 examples

Input notation

k on line 1, followed by k lines of sorted values. An empty line denotes an empty list.

Expected result

Merged values separated by spaces, or empty.

Case 1

Input

Expected output

1 2 3 5 6 7

Case 2

Input

2
4
1 4

Expected output

1 4 4

Case 3

Input

Expected output

empty

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

The first idea is pairwise merge: merge list 1 with 2, then fold in 3, and so on. With N ≤ 10^4 nodes and k ≤ 10^4 lists, the worst case is O(Nk) and can time out. Dumping every node into an array and sorting also works, but ignores that each list is already sorted. The bottleneck is finding the smallest among k heads at every step. A linear scan is O(k) per node and does not fit. At any moment the next node is just the minimum of the current heads. A min-heap of those k heads pops the smallest and pushes its successor. Each node enters and leaves the heap once, so the time is O(Nlog k) and the heap holds at most k pointers.

We can create a min heap pq to maintain the head nodes of all linked lists. Each time, we take out the node with the smallest value from the min heap, add it to the end of the result linked list, and then add the next node of this node to the heap. Repeat the above steps until the heap is empty.

The time complexity is O(n × log k), and the space complexity is O(k). Here, n is the total number of all linked list nodes, and k is the number of linked lists given in the problem.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode head : lists) {
            if (head != null) {
                pq.offer(head);
            }
        }
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            if (node.next != null) {
                pq.offer(node.next);
            }
            cur.next = node;
            cur = cur.next;
        }
        return dummy.next;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.