Leetcode 23. 合并 K 个升序链表 (Day 12)

js一刷 最佳方法

varmerge=function(list1,list2){constdummy=newListNode();letcur=dummy;while(list1&&list2){if(list1.val<list2.val){cur.next=list1;list1=list1.next;}else{cur.next=list2;list2=list2.next;}cur=cur.next;}cur.next=list1?list1:list2;returndummy.next;};varmergeKLists=function(lists){letlen=lists.length;if(len===0)returnnull;if(len===1)returnlists[0];letleft=lists.slice(0,Math.floor(len/2));letright=lists.slice(Math.floor(len/2),len);returnmerge(mergeKLists(left),mergeKLists(right));};

核心还是归并排序
时间复杂度 = O(L log m),其中L是结点树,m是数组长度(如图)

js一刷暴力

varmerge=function(l1,l2){letdummy=newListNode(-Infinity);letcur=dummy;while(l1&&l2){if(l1.val<l2.val){cur.next=l1;l1=l1.next;}else{cur.next=l2;l2=l2.next;}cur=cur.next;}cur.next=l1||l2;returndummy.next;}varmergeKLists=function(lists){lethead=null;for(leti=0;i<lists.length;i++){head=merge(head,lists[i]);}returnhead;};

时间复杂度 = O(L*m)

js 一刷最小堆

varmergeKLists=function(lists){constheap=newMinPriorityQueue(node=>node.val);for(constxoflists){if(x)heap.enqueue(x);}letdummy=newListNode();letcur=dummy;while(!heap.isEmpty()){letnode=heap.dequeue();cur.next=node;if(node.next)heap.enqueue(node.next);cur=cur.next;}returndummy.next;};

要知道 最小堆的api MinPriorityQueue(node=>node.val);
下图pq是最小堆

时间复杂度=O(L log k),每次入堆和出堆操作的复杂度是log k,总共要进行L次操作,L是总结点数