天津市住房和城乡建设厅官方网站建筑管理招聘网

一、前言

23. 合并 K 个升序链表

本题的要求是把K个链表进行合并，合并后的链表必须是从小到大的。

并且这K个链表也是从小到大的升序链表。

---

二、最小堆解法

既然每个链表都是升序的，也就是从小到大的。

那么最后合并出来的链表的第一个节点，也肯定是K个链表的某个链表（记做first链表）第一个节点的其中一个。

合并之后的第二个节点，可以是其余链表的第一个节点或是first链表的第二个节点。

抓住这个规律，我们只需要每次收集每个链表的第一个节点，然后进行排序，取最小那个节点进行合并即可。

如果某个链表的第一个节点已经合并了，那么取第二个。如果第二个也合并了，那么取第三个。以此类推！

这里的话就可以考虑使用最小堆来完成这个排序工作，只需要把节点入堆，然后弹出堆中的最小堆即可。

思路如下：

1. 初始化堆，将K个链表的第一个节点入堆
2. 不断弹出最小堆，直到堆为空为止
   • 对弹出的节点进行合并，如果弹出节点的next不为空，继续将节点的next入堆

public ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);for (ListNode head : lists) {if (head != null){queue.add(head);}}ListNode head = new ListNode();ListNode p0 = head;while (!queue.isEmpty()){ListNode node = queue.poll();p0.next = node;p0 = p0.next;if (node.next != null){queue.add(node.next);}}return head.next;
}

• 时间复杂度： O(nlog⁡k)，其中n为链表总数，k为链表的数量。前面初始化堆的时间复杂度为O(k)，合并链表的时候，从堆中取出最小堆的时间复杂度O(logk)，链表总数为n，链表的所有节点都会放进堆中，因此从堆中取最小堆这个操作需要执行n次，因此时间复杂度为O(nlog⁡k)
• 空间复杂度：O(k)，堆中最多存放k个元素。

---

三、分治解法

分治的思路就是将一个问题拆分成多个子问题，最后将所有子问题进行合并，从而解决问题。

于是我们可以将k个链表分成两个部分，分别为前半部分链表和后半部分链表，先分别对前半部分链表和后半部分链表进行合并成两个升序的链表，然后对升序的两个链表进行合并。

要对前半部分链表和后半部分链表分别合并成两个升序链表，可以继续对这两部分链表进行拆分，一分为二，直到只有一个链表，那就不需要合并了。

因此需要用递归了解决问题

public ListNode mergeKLists(ListNode[] lists) {return mergeKLists(lists, 0, lists.length);
}private ListNode mergeKLists(ListNode[] lists, int i, int j) {int m = j - i;if (m == 0) {return null;}if (m == 1) {return lists[i];}ListNode left = mergeKLists(lists, i, i + m / 2);ListNode right = mergeKLists(lists, i + m / 2, j);return mergeKTwoLists(left, right);
}private ListNode mergeKTwoLists(ListNode left, ListNode right) {ListNode head = new ListNode(-1, null);ListNode p0 = head;while (left != null && right != null) {if (left.val > right.val) {p0.next = right;right = right.next;} else {p0.next = left;left = left.next;}p0 = p0.next;}if (left != null){p0.next = left;}if (right != null){p0.next = right;}return head.next;
}

• 时间复杂度：O(nlogk)。n为链表总数，k为链表数量。分治的时间复杂度为O(logk)，每个节点都要参与一次合并，那么就是O(nlogk).
• 空间复杂度：O(logk)。递归深度为 O(logk)，需要用到 O(logk) 的栈空间。