自助免费建站,萧山网站建设,系统门户,河南郑州建设信息网文章目录 一、前言二、最小堆解法三、分治解法 一、前言 23. 合并 K 个升序链表 本题的要求是把K个链表进行合并#xff0c;合并后的链表必须是从小到大的。
并且这K个链表也是从小到大的升序链表。 二、最小堆解法
既然每个链表都是升序的#xff0c;也就是从小到大的。
… 文章目录 一、前言二、最小堆解法三、分治解法 一、前言 23. 合并 K 个升序链表 本题的要求是把K个链表进行合并合并后的链表必须是从小到大的。
并且这K个链表也是从小到大的升序链表。 二、最小堆解法
既然每个链表都是升序的也就是从小到大的。
那么最后合并出来的链表的第一个节点也肯定是K个链表的某个链表记做first链表第一个节点的其中一个。
合并之后的第二个节点可以是其余链表的第一个节点或是first链表的第二个节点。
抓住这个规律我们只需要每次收集每个链表的第一个节点然后进行排序取最小那个节点进行合并即可。 如果某个链表的第一个节点已经合并了那么取第二个。如果第二个也合并了那么取第三个。以此类推 这里的话就可以考虑使用最小堆来完成这个排序工作只需要把节点入堆然后弹出堆中的最小堆即可。
思路如下
初始化堆将K个链表的第一个节点入堆不断弹出最小堆直到堆为空为止 对弹出的节点进行合并如果弹出节点的next不为空继续将节点的next入堆
public ListNode mergeKLists(ListNode[] lists) {PriorityQueueListNode 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(nlogk)其中n为链表总数k为链表的数量。前面初始化堆的时间复杂度为O(k)合并链表的时候从堆中取出最小堆的时间复杂度O(logk)链表总数为n链表的所有节点都会放进堆中因此从堆中取最小堆这个操作需要执行n次因此时间复杂度为O(nlogk)空间复杂度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) 的栈空间。
