LeetCode题解-合并K个有序数组-Java

利用21题合并两个有序数组的代码，使用for循环进行合并，效率较低；参照第一名的代码，使用分治，改变对数组的处理方法，可以大幅度提高处理效率：

修改后：

public ListNode mergeKLists(ListNode[] lists) {
   
        if(lists==null||lists.length==0)return null;
        return sort(lists, 0, lists.length-1);
    }
public static ListNode sort(ListNode[] lists ,int low , int high) {
   
        if(low>=high) return lists[low];
        int mid = (high - low )/2 + low;
        ListNode l1 = sort(lists ,low , mid);
        ListNode l2 = sort(lists , mid +1 ,high);
        return mergeTwoLists(l1, l2);
}

原：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
   
    public ListNode mergeKLists(ListNode[] lists) {
   
        int length = lists.length;
        if(length==0)return null;
        if(length==1)return lists[0];
        ListNode result = lists[0];
        for(int i = 1 ;i < length; i++) {
   
            result = mergeTwoLists(result, lists[i]);
        }
        return result;
    }
    //重复节点值
    //default关键字修饰变量，在不同包时无法访问
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
   
        ListNode result = new ListNode(0);
        ListNode point = result;
        //{5,1 2 4}
        while(l1!=null&&l2!=null) {
   
                if(l1.val>l2.val) {
   
                    point.next = new ListNode(l2.val);
                    point = point.next;
                    if(l2.next==null||l2.next.val>l1.val) {
   
                        point.next = new ListNode(l1.val);
                        point=point.next;
                        l1=l1.next;
                    }
                    l2=l2.next;
                }else if(l1.val<l2.val){
   
                    point.next = new ListNode(l1.val);
                    point = point.next;
                    if(l1.next==null||l1.next.val>l2.val) {
   
                        point.next = new ListNode(l2.val);
                        point=point.next;
                        l2=l2.next;
                    }
                    l1=l1.next;
                }else {
   
                    point.next = new ListNode(l2.val);
                    point=point.next;
                    point.next = new ListNode(l2.val);
                    point=point.next;
                    l1=l1.next;
                    l2=l2.next;
                }
        }
        while(l1!=null) {
   
            point.next = new ListNode(l1.val);
            point = point.next;
            l1=l1.next;
        }
        while(l2!=null) {
   
            point.next = new ListNode(l2.val);
            point = point.next;
            l2=l2.next;
        }
        return result.next;
    }

}