Merge K Sorted Linked Lists

Given k linked lists, each sorted in ascending order, merge them into one sorted list and return its head.

Example

Text

Input:  [1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6]
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Below, N is the total number of nodes.

Brute force: collect and sort

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    static ListNode mergeKLists(ListNode[] lists) {
        List<Integer> values = new ArrayList<>();
        for (ListNode list : lists) {
            values.addAll(toList(list));
        }
        Collections.sort(values);
        return fromArray(values.stream().mapToInt(Integer::intValue).toArray());
    }

    public static void main(String[] args) {
        ListNode[] lists = {fromArray(1, 4, 5), fromArray(1, 3, 4), fromArray(2, 6)};
        System.out.println(toList(mergeKLists(lists)));
    }
}

Output

[1, 1, 2, 3, 4, 4, 5, 6]

Time: O(N log N). Space: O(N), and it ignores that every list is already sorted.

Optimal: a min-heap of list heads

The next node of the merged list is always the smallest of the k current heads. A min-heap keeps those k candidates, so each choice costs O(log k) instead of comparing all k heads.

The heap stores {value, list index} pairs in int[] arrays. The nodes themselves stay in lists, which avoids making ListNode comparable. After polling index i, detach the head of lists[i], append it to the result, and add the list's new head, if any.

The list nodes use null for "no next node" and have mutable fields, so relinking a node is an assignment. A dummy node before the head removes the special case for the first appended node.

Java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    static ListNode mergeKLists(ListNode[] lists) {
        // each entry is {value of the list's current head, list index}
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            Comparator.comparingInt((int[] e) -> e[0]).thenComparingInt(e -> e[1]));
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) heap.add(new int[]{lists[i].val, i});
        }

        ListNode dummy = new ListNode(0, null); // placeholder before the real head
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            int i = heap.poll()[1];
            ListNode node = lists[i];
            lists[i] = node.next;      // advance this list
            node.next = null;          // detach the node
            if (lists[i] != null) heap.add(new int[]{lists[i].val, i});
            tail.next = node;
            tail = node;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode[] lists = {fromArray(1, 4, 5), fromArray(1, 3, 4), fromArray(2, 6)};
        System.out.println(toList(mergeKLists(lists)));
        System.out.println(toList(mergeKLists(new ListNode[]{null, fromArray(0)})));
        System.out.println(toList(mergeKLists(new ListNode[]{})));
    }
}

Output

[1, 1, 2, 3, 4, 4, 5, 6]
[0]
[]

Time: O(N log k). Space: O(k) for the heap; the nodes are reused.

Adding the k initial entries one by one costs O(k log k), which does not change the total. The tail-pointer technique is the same as in Merge Two Sorted Linked Lists.

Alternative: merge in pairs

Merge list 0 with list 1, 2 with 3, and so on, then repeat on the halved number of lists. Each round touches every node once, and there are log k rounds, so this is also O(N log k) with no heap. Merging the lists one after another into a single growing result is O(N·k) instead, because the early nodes are walked again in every merge.

Edge cases

No lists or only empty lists: the heap starts empty and the result is null.
Duplicates across lists: the comparator breaks ties by list index, so equal values come out in list order.