题目:
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 1:
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2:
输入:lists = []
输出:[]
示例 3:
输入:lists = [[]]
输出:[]
提示:
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
参考@【王尼玛】的解题思路
一、小根堆
如图:4个链表中的最小值,一定来自黄色的部分,黄色的部分就是一个小根堆。
这个堆的元素个数是lists中链表的个数,初始时只是将每个链表的头结点放入堆中,建立完初始的堆后,就不断的从堆中获取节点,如果获取到的节点不为空,即还有下一个节点,那么就将下一个节点放到堆中。
代码:
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode() {} 7 * ListNode(int val) { this.val = val; } 8 * ListNode(int val, ListNode next) { this.val = val; this.next = next; } 9 * } 10 */ 11 class Solution { 12 public ListNode mergeKLists(ListNode[] lists) { 13 if(lists == null || lists.length == 0) return null; 14 PriorityQueue<ListNode> queue = new PriorityQueue(new Comparator<ListNode>(){ 15 public int compare(ListNode l1, ListNode l2){ 16 //升序 17 return l1.val - l2.val; 18 } 19 }); 20 ListNode dummy = new ListNode(0); 21 ListNode cur = dummy; 22 //把每个链表的头结点放进队列中 23 for(ListNode node: lists){ 24 if(node != null){ 25 queue.add(node); 26 } 27 } 28 while(!queue.isEmpty()){ 29 cur.next = queue.poll(); 30 cur = cur.next; 31 //将当前结点的下一个结点也放入队列中 32 if(cur.next != null){ 33 queue.add(cur.next); 34 } 35 } 36 return dummy.next; 37 } 38 }
二、分治和合并
先将整个链表在中间进行拆分成两部分,然后再对这两部分继续拆分,直到拆分成最小单元(只有一个链表)时,再进行两两进行合并,合并后以当前合并后的链表为新的链表再与其他的链表进行合并。看图更容易理解
代码:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists == null || lists.length == 0) return null; return mergeTwolists(lists, 0, lists.length - 1); } //分治 private ListNode mergeTwolists(ListNode[] lists, int start, int end){ if(start == end){ return lists[start]; } int mid = start + (end - start) / 2; ListNode l1 = mergeTwolists(lists, start, mid); ListNode l2 = mergeTwolists(lists, mid+1, end); return merge(l1, l2); } //合并 private ListNode merge(ListNode a, ListNode b){ if(a == null || b == null){ return (a == null) ? b : a; } if(a.val < b.val){ a.next = merge(a.next, b); return a; }else{ b.next = merge(a, b.next); return b; } } }