23. Merge k Sorted Lists

Leetcode: 23. Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:[ 1->4->5, 1->3->4, 2->6 ]
Output: 1->1->2->3->4->4->5->6

/**
 * 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 len=lists.length;
        
        if(lists==null||len==0) return null;
        if(len==1) return lists[0];
        
        while(len>1)//基于“二分”思想进行链表的两两组合
        {
            int mid=(len+1)/2;//二分
            for(int i=0;i<len/2;i++)
            {
                lists[i]=mergeTwoLists(lists[i],lists[i+mid]);
            }
            len=mid;
        }
        return lists[0]; 
    }
    
    private ListNode mergeTwoLists(ListNode listA, ListNode listB) {
        ListNode head = new ListNode(0);
        ListNode tailNode = head;
        if(listA == null) return listB;
        if(listB == null) return listA;
        while(listA != null && listB != null) {
            if(listA.val < listB.val) {
                tailNode.next = listA;
                tailNode = tailNode.next;
                listA = listA.next;
            }
            else {
                tailNode.next = listB;
                tailNode = tailNode.next;
                listB = listB.next;
            }
        }
        if(listA == null) {
            tailNode.next = listB;
        }
        else {
            tailNode.next = listA;
        }
        return head.next;
    }
}