Merge K sorted lists类型题总结

Merge K sorted lists

首先要会做merge 2 sorted lists，这个比较简单，就是使用双指针进行merge。
Merge K sorted lists有两个做法：

• 使用一个list长度的Priority Queue，重新构写Comparator(按照lisstnode.val进行比较)，每次取出最小的listnode以后再向Priority Queue加入新的node。 时间复杂度是O(nlogk)，因为所有的node都要进到PQ中，而每个进去都是O(k)时间。空间复杂度O(k)。
• divide and conquer的思想，因为我们已经做过merge 2 sorted list的题，那么很自然可以想到将list不断地divide直到只剩一个，然后再两个两个的merge，思想与merge sort很像。时间复杂度也是O(nlogk)。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return partition(lists, 0, lists.length-1);
    }
    
    private ListNode partition(ListNode[] lists, int left, int right){
        if(left>right){
            return null;
        }
        else if(left==right){
            return lists[left];
        }
        else{
            ListNode leftPart = partition(lists, left, (left+right)/2);
            ListNode rightPart = partition(lists, (left+right)/2+1, right);
            return merge(leftPart, rightPart);
        }
    }
    
    private ListNode merge(ListNode leftPart, ListNode rightPart){
        //merge two sorted list
        ListNode ans = new ListNode(0);
        ListNode res = ans;
        while(leftPart!=null && rightPart!=null){
            if(leftPart.val<rightPart.val){
                ans.next = leftPart;
                leftPart = leftPart.next;
            }
            else{
                ans.next = rightPart;
                rightPart = rightPart.next;
            }
            ans = ans.next;
        }
        if(leftPart!=null){
            ans.next = leftPart;
        }
        else{
            ans.next = rightPart;
        }
        return res.next;
    }
}