Problem 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: []

Solution

The problem is the extension of LeetCode 21: Merge Two Sorted Lists. It's straightforward to see that the iteration method is not proper here, but we can easily extend the recursion method.

To optimize the extended recursion method, we notice that comparing k numbers costs k operations each time. Thus, we can borrow the PriorityQueue to put k numbers and return the minimum number with the O(lg(k)) time complexity.

Java Code

Recursion

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        if(k == 0) return null;
        if(k == 1) return lists[0];
        int min=0;
        while(min<k && lists[min] == null) min++;
        if(min == k) return null;
        if(min == k-1) return lists[min];
        for(int i=min+1; i<k; i++) {
            if(lists[i] == null) continue;
            min = lists[i].val<lists[min].val ? i : min;
        }
        ListNode head = lists[min];
        lists[min] = lists[min].next;
        head.next = mergeKLists( lists );
        return head;
    }
}

PriorityQueue

public class ListCmp implements Comparator<ListNode>{
    public int compare(ListNode l1, ListNode l2){
        return l1.val - l2.val;
    }
}

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        if(k == 0) return null;
        if(k == 1) return lists[0];
        ListNode head = new ListNode(0), curr=head;
        ListCmp cmp = new ListCmp();
        PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(cmp);
        for(ListNode l:lists) if(l!=null) q.offer(l);
        while( !q.isEmpty() ){
            curr.next = q.poll();
            curr = curr.next;
            if(curr.next != null) q.offer(curr.next);
        }
        return head.next;
    }
}