一、题目描述
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 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
二、思路分析
首先从题目信息我们可以获取两个信息:
- 这里有多个链表,链表数量不是固定的
- 每个链表里的节点都是有序的,而且是升序
然后我们可以发现,想要合并所有的链表,每个链表有一个指针,每次比较获取所有链表中最小的那个节点,添加到新链表中,然后把原链表中的指针往后移一位,接着开始下一轮的比较……重复上述操作,直到所有链表的元素都添加到新链表中……
这里有一个重点,就是如何获取这些链表的最小节点?
最简单暴力的方法就是比较所有的指针指向节点获取最小值,但是循环比较是一个很费时间的操作,如果这样操作的话可能会超时。
那么是不是还有更加优雅的操作呢?
这时候就要考虑能不能缓存每次比较的结果,每次能在缓存的基础上获取最小值呢?这个肯定是有的,就是数据结构中的堆,我们可以使用小顶堆获取每轮比较的最小节点。
堆在Java中有可以直接使用的封装类——优先队列,我们可以实现一下比较方法,然后决定这是小顶堆,还是大顶堆。
代码实现
class Solution {
// 实现比较器,通过节点的值做比较
static Comparator<ListNode> comparator = new Comparator<ListNode>() {
public int compare(ListNode e1, ListNode e2) {
return e1.val - e2.val;
}
};
public ListNode mergeKLists(ListNode[] lists) {
// 实现小顶堆
PriorityQueue<ListNode> queue = new PriorityQueue<>(comparator);
ListNode ans = new ListNode();
ListNode moveNode = ans;
// 把非空的链表头节点添加到优先队列
for (ListNode list : lists) {
if (list != null) {
queue.offer(list);
}
}
// 队列不为空的时候继续比较
while (!queue.isEmpty()) {
moveNode.next = queue.poll();
if (moveNode.next.next != null) {
queue.offer(moveNode.next.next);
}
moveNode = moveNode.next;
}
return ans.next;
}
}
总结
- 这种题主要是考察了数据结构中一些常用数据结构的性质,平时要多加熟悉,才能更好的运用在实际中。
- 一般遇到一堆无序数据中的最大值,最小值,第K大的值,可以优先考虑一下堆。