LeetCode Java刷题笔记—23. 合并K个升序链表

23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

困难难度。这道题是21. 合并两个有序链表的变种，但是难度提升了很多，一般来说两种方式，一是分治法两两合并，时间复杂度O(kn×logk)，空间复杂度O(logk)。二是最小堆优先级队列。时间复杂度O(nklogk)。

最小堆可以直接使用PriorityQueue这个线程的优先级队列。思路还是很简单的，我们将所有链表头节点都放进去，然后开始循环出堆，此时出来的元素就是最小的一个元素，然后将出堆节点的next再次加入到最小堆中即可。

public ListNode mergeKLists( ListNode[] lists ){

   if( lists == null || lists.length == 0 ){
      return null;
   }
   //构建最小堆
   PriorityQueue<ListNode> queue = new PriorityQueue<>( ( o1, o2 ) -> o1.val - o2.val );
   ListNode dummy = new ListNode( 0 );
   ListNode p = dummy;
   //所有头节点加入堆
   for( ListNode node : lists ){
      if( node != null ) queue.add( node );
   }
   //堆排序
   while( !queue.isEmpty() ){
      //取出最小节点
      p.next = queue.poll();
      p = p.next;
      //最小节点的后继不为null，则将后继加入最小堆
      if( p.next != null ){
         queue.add( p.next );
      }
   }
   return dummy.next;
}