// @Title: 合并 K 个升序链表 (Merge k Sorted Lists)
// @Author: qisiii
// @Date: 2024-04-13 16:42:20
// @Runtime: 4 ms
// @Memory: 44.5 MB
// @comment: 
// @flag: 
/**
 * 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) {
        if (lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        ListNode left = mergeKLists(Arrays.copyOfRange(lists, 0, lists.length / 2));
        ListNode right = mergeKLists(Arrays.copyOfRange(lists, lists.length / 2, lists.length));
        return mergeTwo(left, right);
    }

    public ListNode mergeTwo(ListNode one, ListNode two) {
        if (one == null) {
            return two;
        }
        if (two == null) {
            return one;
        }
        ListNode result = new ListNode(-1);
        ListNode temp = result;
        while (one != null && two != null) {
            if (one.val < two.val) {
                temp.next = new ListNode(one.val);
                one = one.next;
                temp = temp.next;
            } else {
                temp.next = new ListNode(two.val);
                two = two.next;
                temp = temp.next;
            }
        }
        if (one == null) {
            temp.next = two;
        } else {
            temp.next = one;
        }
        return result.next;
    }
}