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

最优解法，Merge with Divide And Conquer，

这种解法通过把list里的链表两两合并，把时间复杂度降到了O(nLogk)，k是一共有几个pair两两合并

Time complexity : O(N\log k)O(Nlogk) where \text{k}k is the number of linked lists.

• We can merge two sorted linked list in O(n)O(n) time where nn is the total number of nodes in two lists.

• Sum up the merge process and we can get: O\big(\sum_{i=1}^{log_{2}{k}}N \big)= O(N\log k)O(∑​i=1​log​2​​k​​N)=O(Nlogk)

Space complexity : O(1)O(1)

• We can merge two sorted linked lists in O(1)O(1) space.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0 || lists == null){
            return null;
        }
        
        return mergeHelper(lists,0,lists.length -1);
        
    }
    
    public ListNode mergeHelper(ListNode[] lists,int start, int end){
        if(start == end){
            return lists[start];
        }
        
        int mid = start + (end - start )/2;
        ListNode left = mergeHelper(lists, start,mid);
        ListNode right = mergeHelper(lists,mid+1,end);
        
        return mergeTwoList(left,right);
        
    }
    
    public ListNode mergeTwoList(ListNode list1,ListNode list2){
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                tail.next = list1;
                tail = list1;
                list1 = list1.next;
            }else{
                tail.next = list2;
                tail = list2;
                list2 = list2.next;
            }
        }
        
        if(list1 != null){
            tail.next = list1;
        }else{
            tail.next = list2;
        }
        
        return dummy.next;
    }
}