题目
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
思路
- 使用优先队列并实现comparator接口
- 开辟带有头节点的新链表foo
- 当队列不为空时，将最小链表出队并与foo建立关联，将foo后移 ，如果不为空则将foo的第二个及后续节点放入队列中再次循环
- 当队列为空时，返回foo即为合并后的新链表
核心代码
while (!queue.isEmpty()) {
cur.next = queue.poll();//将较小的出队并建立关联
cur = cur.next;//从头节点移到首节点
if (cur.next != null) {
queue.add(cur.next);//将第二个节点及以后节点重新放入队列中
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
for (ListNode list : lists) {
if (list != null) {
queue.add(list);
}
}
while (!queue.isEmpty()) {
cur.next = queue.poll();//将较小的出队并建立关联
cur = cur.next;//从头节点移到首节点
if (cur.next != null) {
queue.add(cur.next);//将第二个节点及以后节点重新放入队列中
}
}
return dummy.next;
}
}
