23. Merge k Sorted Lists (Hard)

https://leetcode.com/problems/merge-k-sorted-lists/

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

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

Solutions

1.

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }

        ListNode pointer;

        // Get the total number of the nodes
        int size = 0;
        for (int i = 0; i < lists.length; i++) {
            pointer = lists[i];
            while (pointer != null) {
                size += 1;
                pointer = pointer.next;
            }
        }

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

        while ((size--) > 0) {
            int index = -1;
            int min = Integer.MAX_VALUE;

            // Walk through the heads of visited stored in lists and find out the minDelete value
            // and corresponding index in the list
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] == null) {
                    continue;
                }

                if (lists[i].val < min) {
                    min = lists[i].val;
                    index = i;
                }
            }

            pointer.next = lists[index];
            pointer = pointer.next;

            // Move the header of lists[index] to the next
            lists[index] = lists[index].next;

            pointer.next = null;
        }

        return dummy.next;
    }
}

2.

class Solution {

    // With the help of PriorityQueue, we just pump values into the queue and
    // don't have to take the order issue into consideration.

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }

        // Used to keep the values in ascending order
        Queue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));

        // insert into priority queue and the elements are sorted automatically
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] == null) {
                continue;
            }

            ListNode node = lists[i];
            while (node != null) {
                queue.add(node);
                node = node.next;
            }
        }

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

        // poll all the elements in order and append them to a linked list
        while (queue.peek() != null) {
            pointer.next = queue.poll();
            pointer = pointer.next;
        }

        pointer.next = null;

        return dummy.next;
    }
}

Incorrect Solutions

References