[leetcode]23. Merge k Sorted Lists归并k个有序链表

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

1 Input: 2 [ 3 1->4->5, 4 1->3->4, 5 2->6 6 ] 7 Output: 1->1->2->3->4->4->5->6

 

题意：

归并k个有序链表。

 

思路：

用一个最小堆minHeap，将所有链表的头结点放入

新建一个linkedlist存储结果

minHeap里面每remove一个node（最小堆保证了该元素为当前堆中最小）， 就加到新建linkedlist中，并将该node.next加入到堆里

  

代码：

 

1 class Solution { 2 public ListNode mergeKLists(ListNode[] lists) { 3 // special case 4 if(lists.length==0) return null; 5 6 //1. priorityqueue ((o1,o2)-> o1.val, o2.val) acsending order 7 PriorityQueue<ListNode> heap = new PriorityQueue<>((o1,o2)-> o1.val-o2.val); 8 9 //add each list's each node into the heap, in acsending order 10 int size = lists.length; 11 for(int i = 0; i<size; i++){ 12 if(lists[i]!=null){ 13 heap.add(lists[i]); //注意这步操作直接把list的每个节点都扔进了heap 14 15 } 16 } 17 //2. create a new linkedlist 18 ListNode fakeHead = new ListNode(-1); 19 ListNode current = fakeHead; 20 21 //3. add every node from priorityqueue's removing 22 while(heap.size()!=0){ 23 ListNode node = heap.remove(); 24 current.next = node; 25 current=current.next; 26 if(node.next!=null) heap.add(node.next); 27 } 28 return fakeHead.next; 29 } 30 }

 

 

 

转载于:https://www.cnblogs.com/liuliu5151/p/9158321.html