上海医疗旅游开发网站建设/武汉今日新闻头条

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[1->4->5,1->3->4,2->6
]
输出: 1->1->2->3->4->4->5->6

对于两个有序链表，我们直接进行遍历就可以做出来，但是多个就得使用堆进行排序，先将N个有序链表的头节点放入堆中，建一个小堆。每次在输出一个有序链表的节点后，加入他的后一个结点。就可以达到遍历所有结点的效果。

class Solution {public ListNode mergeKLists(ListNode[] lists) {ListNode dummy = new ListNode(0);ListNode cur = dummy;PriorityQueue<ListNode> pq = new PriorityQueue<>((ListNode l1,ListNode l2)->(l1.val-l2.val));for(ListNode list:lists){if(list != null)pq.offer(list);}while(!pq.isEmpty()){ListNode next = pq.poll();cur.next = next;cur = cur.next;if(next.next != null){pq.offer(next.next);}}return dummy.next;}
}