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

先解决子问题 两个链表合并

使用归并思路合并K个链表

 * 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.size() ==0){
            return null;
        }
        int len = lists.size();
      return  merge(lists,0,len-1);
        
    }
    
     public ListNode merge(ArrayList<ListNode> lists , int left ,int right){
          
         if(left == right){
           return  lists.get(left);
         }
         if(left >right){
             return null;
         }
         int mid = left +(right -left)/2;
         
         ListNode leftNode = merge(lists,left,mid);
         ListNode rightNode = merge(lists,mid+1,right);
         
         return mergeTwo(leftNode,rightNode);
     }
    
    public ListNode mergeTwo(ListNode left,ListNode right){
        if(left == null && right == null){
            return left;
        }
        if(left == null){
            return right;
        }
        if(right == null){
            return left;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while(left != null && right != null){
            if(left.val <= right.val){
                tail.next = left;
                left = left.next;
            
            }else{
                tail.next = right;
                right = right.next;
            }
            tail = tail.next;
        }
        tail.next = left == null?right:left;
        return head.next;
    }
}