一、题目

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

点击查看原题
难度级别： 困难

二、思路

1）暴力法，找出k个链表最小值并组合

确定一个函数findMin，该函数遍历寻找k个链表的最小值，因为链表内部升序排列，只需要比较每条链表头部元素即可。找到后挨个组合成合并的链表

2）手写优先队列合并

将k个链表的头节点放置于一个List中，并根据值进行从小到大的排序
每次取出第一个链表头节点加入合并链表中，并往后遍历，直到它值大于List中的第二个链表头节点
然后将该合并链表的end后一个节点，找到合适位置插入（维持List中从小到大的排序），反复上述过程

3）分治法

先写出两个链表合并的函数mergeTwo
再根据分治法的思想，对k个链表，使用函数mergeTwo进行合并

三、代码

1）暴力法，找出k个链表最小值并组合

class Solution {
    private int k = 0;
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = new ListNode();
        ListNode end = ans;
        if (lists == null || lists.length == 0) {
            return ans.next;
        }
        k = lists.length;    // 跳出条件，当lists中没有元素就跳出
        while (k > 0) {
            ListNode node = findMin(lists);
            end.next = node;
            end = node;
        }
        return ans.next;
    }
    private ListNode findMin(ListNode[] lists) {
        int loc = 0;
        while (loc < lists.length && lists[loc] == null) {    // 找到第一个不为null的元素
            loc++;
        }
        if (loc == lists.length) {    // 遍历了一圈，发现lists中没有元素，如[[null]]的情况
            k = 0;
            return null;
        }
        for (int i = loc + 1; i < lists.length; i++) {    // 找最小值
            if (lists[i] != null && lists[i].val < lists[loc].val) {
                loc = i;
            }
        }
        ListNode ans = lists[loc];
        lists[loc] = ans.next;
        if (ans.next == null) {    // 发现一条链没有元素了，让k自减
            k--;
        }
        return ans;
    }
}

k为链表个数，n为链表平均长度，时间复杂度为O(k*k*n)，空间复杂度为O(k)

2）手写优先队列合并

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = new ListNode();
        ListNode end = ans;
        List<ListNode> headers = new LinkedList();
        if (lists == null || lists.length == 0) {
            return ans.next;
        }
        for (ListNode node : lists) {    // 将链表放置如头节点链表中
            if (node != null) {
                headers.add(node);
            }
        }
        Collections.sort(headers, (ListNode n1, ListNode n2)-> {    // 排序
            if (n1.val == n2.val) {
                return 0;
            }
            return n1.val > n2.val ? 1 : -1;
        });
        while (headers.size() != 0) {
            end.next = headers.get(0);
            end = end.next;        // 当插入此节点，节点所在链表的后续节点也可以通过end遍历访问
            headers.remove(0);
            if (headers.size() != 0) {
                // 找到end所在链上节点大于header中第一个节点值
                while (end.next != null && headers.get(0).val > end.next.val) {
                    end = end.next;
                }
                if (end.next == null) {    // end链上节点遍历完也没有找到大于header中第一个节点值
                    continue;
                }
                int insertLoc = 0;
                // 将找到的节点插入它应该在的位置，寻找该位置
                while (insertLoc < headers.size() && headers.get(insertLoc).val < end.next.val) {
                    insertLoc++;
                }
                headers.add(insertLoc, end.next);
            }
        }
        return ans.next;
    }
}

k为链表个数，n为链表平均长度，时间复杂度为O(k*k*n)，空间复杂度为O(k)，这里算法比上一个好，是因为上一个每添加一个节点固定需要访问k次进行对比，这里不需要固定访问k次，较好的情况只需比较1一次，就可以确定，最差情况才是k次比较

3）分治法

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return mergeAll(lists, 0, lists.length - 1);
    }
    private ListNode mergeAll(ListNode[] lists, int left, int right) {
        if (left > right) {
            return null;
        }
        if (left == right) {
            return left < lists.length ? lists[left] : null;
        }
        int mid = (left + right)/2;
        return mergeTwo(mergeAll(lists, left, mid), mergeAll(lists, mid + 1, right));
    }
    private ListNode mergeTwo(ListNode n1, ListNode n2) {
        ListNode ans = new ListNode();
        ListNode end = ans;
        while (n1 != null && n2 != null) {
            if (n1.val < n2.val) {
                end.next = n1;
                n1 = n1.next;
            } else {
                end.next = n2;
                n2 = n2.next;
            }
            end = end.next;
        }
        end.next = (n1 != null) ? n1 : n2;
        ListNode t = ans.next;
        return ans.next;
    }
}

k为链表个数，n为链表平均长度，时间复杂度为O(k*n*logk)，空间复杂度为O(logk)