0023. Merge k Sorted Lists

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

Description

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 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 <= 10^4

• 0 <= lists[i].length <= 500

• -10^4 <= lists[i][j] <= 10^4

• lists[i] is sorted in ascending order.

• The sum of lists[i].length won't exceed 10^4.

ac1: heap sort

O(Nlogk): N is the total amount of nodes, k is the length of lists

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // build priority heap
        // always take lists[0]
        // if lists[0] == null, swap to tail, reduce 1 loop
        // heapify(list[0])

        // corner cases
        if (lists.length == 0) return null;
        if (lists.length == 1) return lists[0];

        // build binary heap
        for (int i = lists.length - 1; i >= 0; i--) {
            heapify(lists, i);
        }

        // dummy node take result;
        ListNode dummy = new ListNode(0);
        ListNode d = dummy;

        // loop
        for (int k = lists.length-1; k > 0; k--) {
            while (lists[0] != null) {
                heapify(lists, 0);
                d.next = lists[0];
                d = d.next;
                lists[0] = lists[0].next;
            }
            ListNode tmp = lists[k];
            lists[k] = lists[0];
            lists[0] = tmp;
        }
        d.next = lists[0];

        return dummy.next;
    }
    private void heapify(ListNode[] lists, int i) {
        int min = i, l = 2*i+1, r = 2*i+2, n = lists.length;

        // compare root & left;
        if (l < n && lists[l] != null) {
            if (lists[min] == null || lists[l].val < lists[min].val) {
                min = l;
            }
        }

        // compare right & min
        if (r < n && lists[r] != null) {
            if (lists[min] == null || lists[r].val < lists[min].val) {
                min = r;
            }
        }

        // swap?
        if (min == i || lists[min] == null) {
            return; // already min, no need to swap.
        } else {

        // swap root & minIdx
            ListNode tmp = lists[i];
            lists[i] = lists[min];
            lists[min] = tmp;
        }

        // heapify minIdx
        heapify(lists, min);
    }
}

AC2: priority queue

https://leetcode.com/problems/merge-k-sorted-lists/discuss/10528/A-java-solution-based-on-Priority-Queue

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(0);
        ListNode r = dummy;

        // PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> {return a.val - b.val;});
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            public int compare(ListNode l1, ListNode l2) {
                return l1.val - l2.val;
            }
        });
        for (ListNode n : lists) {
            if (n != null) pq.offer(n);
        }

        while (pq.size() > 1) {
            ListNode curr = pq.poll();
            r.next = curr;
            r = r.next;
            if (curr.next != null) pq.offer(curr.next);
        }

        if (pq.size() == 1) {
            r.next = pq.poll();
        }

        return dummy.next;
    }
}

other solutions

• divide & conquer, O(Nlogk)