题目

https://leetcode-cn.com/problems/merge-k-sorted-lists/description/

递归方式

/**
 * 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;
        }
         
        if(lists.length==1){
            return lists[0];
        }
        if(lists.length==2){
            return merge(lists[0],lists[1]);
        } 
    
        return merge(lists[0], mergeKLists(Arrays.copyOfRange(lists,1,lists.length)) );
    }

    private ListNode merge(ListNode list1, ListNode list2){
        ListNode dummy=new ListNode(0);
        ListNode p = dummy;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                p.next=list1;
                list1=list1.next;
            }else{
                p.next=list2;
                list2=list2.next;
            }
            p=p.next;
        }
        if(list1!=null){
            p.next=list1;
        }
        if(list2!=null){
            p.next=list2;
        }
        return dummy.next;
    }
    
}

非递归的方式

 private ListNode mergeB(ListNode[]list){
        if(list==null||list.length==0){
            return null;
        }
        if(list.length==1){
            return list[0];
        }

        ListNode head = merge(list[0],list[1]);
        for(int i=2;i<list.length;i++){
            head = merge(head, list[i]);
        }
        return head;
    }

// merge 方法同上