题解 | #合并k个已排序的链表#TOP5

思路： 自顶向下，这叫归并排序。我们要合并一定范围[start,end]的节点，拆成[start,mid], (mid,end] 两部分节点合并，将这两部分排好序的合并就ok了。然后继续拆解。

 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists == null || lists.isEmpty()){
            return null;
        }
        //1、新建一个ListNode 然后每次遍历 list.size() 找出最小，时间复杂度 mO(N) 控件复杂度 m
        //2、不断循环遍历 每次 合并2个ListNode
        //3. 类似二分法 从上到下，再从下到上
        return mergeKLists(lists,0,lists.size() - 1);
    }
    public ListNode mergeKLists(ArrayList<ListNode> lists,int low,int high){
        if(high <= low){
            return lists.get(low);
        }
        int mid = low + (high - low) / 2;
        ListNode left = mergeKLists(lists,low,mid);
        ListNode right = mergeKLists(lists,mid + 1,high);
        return mergeTwoLists(left, right);
    }
 
    private ListNode mergeTwoLists(ListNode left, ListNode right){
        if(left == null ){
            return right;
        }
        if(right == null){
            return left;
        }
        ListNode temp = new ListNode(0);
        ListNode currentNode = temp;
        while(left != null && right != null){
            if(left.val < right.val){
                currentNode.next = left;
                left = left.next;
            }else{
                currentNode.next = right;
                right = right.next;
            }
            currentNode = currentNode.next;
        }
        currentNode.next = left == null ? right :left;
        return temp.next;
    }
    
    
    
    
    
}