Merge K Sorted Linked Lists

NeetCode: Merge K Sorted Linked Lists · LeetCode: 23. Merge K Sorted Linked Lists · Difficulty: Hard

Given k sorted linked lists, merge them into one sorted list.

Example

Text

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

Java linked structures use null and mutable fields, so each list is a chain of ListNode objects and the empty list is null. The helper fromArray builds a list from its values and toList copies a list into an ArrayList for printing. LeetCode passes the lists as a ListNode[].

Brute force: collect everything, sort

Java

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

class ListNode {
    int val;
    ListNode next;

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

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

public class Main {
    static ListNode fromArray(int... values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            out.add(cur.val);
        }
        return out;
    }

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

Output

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

Time: O(N log N) for N total nodes. Space: O(N).

Optimal: min-heap of list heads

At any moment the smallest remaining value is the head of one of the k lists. Keep those k heads in a min-heap ordered by value. Pop the smallest, append its node to the result, and push that node's next. The heap never holds more than k items, so each of the N pops costs O(log k).

PriorityQueue is a min-heap, so the comparator Comparator.comparingInt(n -> n.val) orders nodes by value. Subtracting values in a hand-written comparator can overflow, so comparingInt is used. The heap rejects null, so empty lists are skipped when the heap is filled. Nodes with equal values may leave the heap in either order, which does not change the merged values.

Java

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

class ListNode {
    int val;
    ListNode next;

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

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt((ListNode n) -> n.val));
        for (ListNode head : lists) {
            if (head != null) {
                heap.offer(head);
            }
        }
        ListNode dummy = new ListNode(0);
        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;
    }
}

public class Main {
    static ListNode fromArray(int... values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            out.add(cur.val);
        }
        return out;
    }

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

Output

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

Time: O(N log k). Space: O(k) for the heap.

Merging the lists pairwise, as in merge sort, also runs in O(N log k) and reuses Merge Two Sorted Linked Lists.