输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

输入：lists = []
输出：[]

输入：lists = [[]]
输出：[]

package ski.mashiro.leetcode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class _23 {
    /**
     * 23. 合并K个升序链表
     * <p>
     * 给你一个链表数组，每个链表都已经按升序排列。
     * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
     */
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode l3 = new ListNode(2, new ListNode(6));
        ListNode listNode = mergeKLists(new ListNode[]{l1, l2, l3});
        while (listNode != null) {
            System.out.print(listNode.val + ", ");
            listNode = listNode.next;
        }
    }

    /**
     * 分治
     * 每次将两个链表合并成一个
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    private static ListNode merge(ListNode[] lists, int left, int right) {
//        左右指针指向同一元素，直接返回
        if (left == right) {
            return lists[left];
        }
//        因为mid + 1，有可能发生左指针大于右指针的情况
//        返回null
        if (left > right) {
            return null;
        }
//        注释的是问题代码，目测是在向下舍入的时候有精度问题，导致无限递归
//        int mid = (right - left) >> 1 + left;
        int mid = (left + right) >> 1;
//        递归调用，递归返回数组的元素或是null，两者再进行合并，返回到上层递归称为参数
        return mergeTwoListNode(merge(lists, left, mid), merge(lists, mid + 1, right));
    }


    /**
     * 法二
     * 新建一个链表，每次将新链表和数组内的一个链表合并
     */
    public static ListNode mergeKLists2(ListNode[] lists) {
        List<Integer> list = new ArrayList<>(lists.length * 5);
        ListNode rs = null;
        for (ListNode listNode : lists) {
            rs = mergeTwoListNode(rs, listNode);
        }
        return rs;
    }

    private static ListNode mergeTwoListNode(ListNode list1, ListNode list2) {
        ListNode rs = new ListNode();
        ListNode cur = rs;
        while (list1 != null || list2 != null) {
            if (list1 != null && list2 != null) {
                if (list1.val < list2.val) {
                    cur.next = list1;
                    list1 = list1.next;
                } else {
                    cur.next = list2;
                    list2 = list2.next;
                }
            } else if (list1 != null) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        return rs.next;
    }

    /**
     * 法三
     * 转换成集合处理
     */
    public static ListNode mergeKLists3(ListNode[] lists) {
        List<Integer> list = new ArrayList<>(lists.length * 5);
        for (ListNode listNode : lists) {
            while (listNode != null) {
                list.add(listNode.val);
                listNode = listNode.next;
            }
        }
        list.sort(Comparator.comparingInt(o -> o));
        ListNode rs = new ListNode();
        ListNode cur = rs;
        for (Integer item : list) {
            cur.next = new ListNode(item);
            cur = cur.next;
        }
        return rs.next;
    }

    private static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}