24. Merge K ascending linked lists

23. Merge K An ascending list

Here's an array of linked lists , Each list has been listed in ascending order .

Please merge all the linked lists into one ascending list , Return the merged linked list .

Example 1：

 Input ：lists = [[1,4,5],[1,3,4],[2,6]]
 Output ：[1,1,2,3,4,4,5,6]
 explain ： The linked list array is as follows ：
[
  1->4->5,
  1->3->4,
  2->6
]
 Combine them into an ordered list to get .
1->1->2->3->4->4->5->6

Example 2：

 Input ：lists = []
 Output ：[]

Example 3：

 Input ：lists = [[]]
 Output ：[]

Divide and conquer algorithm

1: Divide and conquer , First the K The linked list is divided into two parts , Merge the two parts first , The linked list returned after merging these two parts .

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
    
        ListNode ans = null;
        for(int i=0;i<lists.length;i++){
    
            ans = merge(ans,lists[i]);
        }
        return ans;
    }

    public ListNode merge(ListNode a,ListNode b){
    
        if(a==null||b==null){
    
            return a!=null?a:b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head,p = a,q =b;
        while(p!=null&&q!=null){
    
            if(p.val>=q.val){
    
                ListNode c = new ListNode(q.val);
                tail.next = c;
                tail = c;
                q = q.next;
            }
            else{
    
                ListNode c = new ListNode(p.val);
                tail.next = c;
                tail = c;
                p = p.next;
            }
        }
        if(p!=null) tail.next = p;
        if(q!=null) tail.next = q;
        return head.next;
    }
}