LeetCode-Algorithms-[Hard]23. 合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

解法一：
思想是先“全部拿出来”，再放进去，很自然想到小根堆

当然如果题目给出了数据范围，也可以考虑桶排序

    public ListNode mergeKLists(ListNode[] lists) {
        Queue<Integer> queue = new PriorityQueue<>();
        for (ListNode listNode : lists) {
            while (listNode != null) {
                queue.offer(listNode.val);
                listNode = listNode.next;
            }
        }
        ListNode head = new ListNode(0);
        ListNode current = head;
        while (!queue.isEmpty()) {
            int val = queue.poll();
            ListNode currentNode = new ListNode(val);
            current.next = currentNode;
            current = currentNode;
        }
        return head.next;
    }

解法二：

链表两两合并的思想

    public ListNode mergeKLists_2(ListNode[] lists) {
        int n = lists.length;
        if (n == 0) {
            return null;
        }
        return mergeKLists(lists, 0, n);
    }

    private ListNode mergeKLists(ListNode[] lists, int low, int high) {
        if (low == high - 1) {
            return lists[low];
        }
        int mid = low + ((high - low) >> 1);
        ListNode l1 = mergeKLists(lists, low, mid);
        ListNode l2 = mergeKLists(lists, mid, high);
        return mergeListNode(l1, l2);
    }

    public ListNode mergeListNode(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode current = head;
        ListNode newNode;
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                newNode = new ListNode(l2.val);
                l2 = l2.next;
            } else {
                newNode = new ListNode(l1.val);
                l1 = l1.next;
            }
            current.next = newNode;
            current = newNode;
        }
        current.next = l1 != null ? l1 : l2;
        return head.next;
    }

本文地址：https://blog.csdn.net/m0_37302219/article/details/107353764