leetcode 23. Merge k Sorted Lists

Seawolf

用二叉堆来优化：

/**
 * 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 == null || lists.length == 0){
            
            return null;
            
        }
    
        PriorityQueue <ListNode> queue = new PriorityQueue<ListNode>(lists.length, (a,b) -> a.val - b.val);
        
        for(ListNode e: lists){
            
            if(e != null){
                
                queue.add(e);
                
            }
            
        }
        
        ListNode ptr = new ListNode(0);
        
        ListNode head = ptr;
        
        while(!queue.isEmpty()){
            
            ptr.next = queue.poll();
            
            ptr = ptr.next;
            
            if(ptr.next != null){
                
                queue.add(ptr.next);
                
            }
            
            
        }
        
        return head.next;
        
    }
    
}

    

用 divide and conquer：

/**
 * 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){
            
            return null;
        }
        
        if(lists.length == 1){
            
            return lists[0];
        }
        
        if(lists.length == 2){
            
            return mergeSort(lists[0],lists[1]);
        }
        
        
        int mid;
        
        ListNode[] sublist1;
        
        ListNode[] sublist2;
        
        if(lists.length % 2 ==0){
            
            mid = lists.length/2;
        
            sublist1 = new ListNode[mid];
        
            sublist2 = new ListNode[mid];
            
        }
        else{
        
            mid = lists.length/2;
        
            sublist1 = new ListNode[mid];
        
            sublist2 = new ListNode[mid+1];
            
        }
        
        for(int i = 0 ; i< mid ; i++){
            
            sublist1[i]  = lists[i];
            
        }
        
        
        int count = 0;
        
        for(int i = mid ; i< lists.length ; i++){
            
            sublist2[count] = lists[i];
            
            count++;
            
        }
        
        ListNode l1 = mergeKLists(sublist1);
        
        ListNode l2 = mergeKLists(sublist2);
        
        return mergeSort(l1,l2);
        
    }
    
    private static ListNode mergeSort(ListNode l1, ListNode l2){
        
        ListNode ptr = new ListNode(0);
            
        ListNode head = ptr;
        
        while(l1 != null || l2 != null){
            
            if(l2 == null || (l1 != null && l2.val >= l1.val)){
                
                ptr.next = l1;
                
                l1 = l1.next;
                
                ptr = ptr.next;
                
                
            }
            else if (l1 == null || (l2 != null && l1.val > l2.val)){
                
                ptr.next = l2;
                
                l2 = l2.next;
                
                ptr = ptr.next;
                
            }
            
                
        }
        
        return head.next;
        
    }
    
}