一侧巨、問(wèn)題描述
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

二逾柿、解決思路
思路一：直接通過(guò)循環(huán)跋选，每次求出鏈表數(shù)組中最小節(jié)點(diǎn)直到結(jié)束
思路二：對(duì)于合并數(shù)組元素，可以考慮到使用分治思想尝哆，先兩兩分出來(lái)，然后再治理合并
思路三：參考solution思想，自己實(shí)現(xiàn)一個(gè)比較器，并使用優(yōu)先隊(duì)列（能利用現(xiàn)有框架般码，否則就要自己造輪子）構(gòu)建最小堆來(lái)實(shí)現(xiàn)

三、算法實(shí)現(xiàn)
思路一

public ListNode mergeKLists(ListNode[] lists) {
        // 哨兵節(jié)點(diǎn)
        ListNode head = new ListNode(0);
        ListNode pre = head;
        while(!checkNull(lists)){
            ListNode n1 = check3Null(lists);
            if(n1 == null){
                if(get4Null(lists) != lists.length){
                    ListNode n2 = getListNode(lists);
                    //System.out.println("ts = " + n2.val);
                    head.next = n2;
                    head = head.next;
                }
            } else {
                head.next = n1;
                break;
            }
        }
        return pre.next;
    }
    public ListNode getListNode(ListNode[] lists){
        ListNode node = null;
        int idx = 0;
        for(int i = 0; i < lists.length; i++){
            ListNode n = lists[i];
            if(n != null){
                if(node == null){
                    node = n;
                    idx = i;
                } else {
                    if(n.val < node.val){
                        node = n;
                        idx = i;
                        //n = n.next;
                    }
                }
            }
        }
        ListNode res = node;
        ListNode tmp = lists[idx];
        lists[idx] = tmp.next;
        return res;
    }
    public int get4Null(ListNode[] lists){
        int sum = 0;
        for(ListNode node : lists){
            if(node == null){
                sum++;
            }
        }
        return sum;
    }
    public ListNode check3Null(ListNode[] lists){
        int sum = 0;
        int idx = 0;
        for(int i = 0; i < lists.length; i++){
            ListNode node = lists[i];
            if(node == null){
                sum++;
            } else {
                idx = i;
            }
        }
        if(sum == lists.length - 1){
            return lists[idx];
        }
        return null;
    }
    public boolean checkNull(ListNode[] list){
        for(ListNode node : list){
            if(node != null){
                return false;
            }
        }
        return true;
    }

思路二

public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 1) return lists[0];
        if(lists.length == 0) return null;
        while(lists.length > 1){
            int lens = lists.length;
            ListNode[] arr = null;
            if((lens & 1) == 1){
                arr = new ListNode[lens / 2 + 1];
                int idx = 0;
                for(int i = 0; i < (lens - 1) / 2; i++){
                    ListNode p = mergeTwoLists(lists[2 * i], lists[2 * i + 1]);
                    arr[idx++] = p;
                }
                arr[idx] = lists[lens - 1];
                lists = arr;
            } else {
                arr = new ListNode[lens / 2];
                int idx = 0;
                for(int i = 0; i < lens / 2; i++){
                    ListNode p = mergeTwoLists(lists[2 * i], lists[2 * i + 1]);
                    arr[idx++] = p;
                }
                lists = arr;
            }
        }
        return lists[0];
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode head = null;
        if(l1.val < l2.val){
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }

思路三

Comparator<ListNode> cmp = new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        };
        ListNode head = new ListNode(0);
        ListNode pre = head;
        Queue<ListNode> queue = new PriorityQueue<>(cmp);
        for(ListNode node : lists){
            if(node != null){
                queue.add(node);
            }
        }
        while(!queue.isEmpty()){
            ListNode node = queue.poll();
            head.next = node;
            head = head.next;
            if(node != null){
                if(node.next != null){
                    queue.add(node.next);
                }
            }
        }
        return pre.next;