Time: 4 ms (75.52%), Space: 44.5 MB (40.37%) - LeetHub

py3-coder · py3-coder · commit 4878513ac196 · 2024-11-05T23:46:36.000+05:30
diff --git a/0023-merge-k-sorted-lists/0023-merge-k-sorted-lists.java b/0023-merge-k-sorted-lists/0023-merge-k-sorted-lists.java
@@ -8,32 +8,30 @@
  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  * }
  */
-public class Solution {
-    public static ListNode mergeKLists(ListNode[] lists){
-    return partion(lists,0,lists.length-1);
-}
-
-public static ListNode partion(ListNode[] lists,int s,int e){
-    if(s==e)  return lists[s];
-    if(s<e){
-        int q=(s+e)/2;
-        ListNode l1=partion(lists,s,q);
-        ListNode l2=partion(lists,q+1,e);
-        return merge(l1,l2);
-    }else
-        return null;
-}
-
-//This function is from Merge Two Sorted Lists.
-public static ListNode merge(ListNode l1,ListNode l2){
-    if(l1==null) return l2;
-    if(l2==null) return l1;
-    if(l1.val<l2.val){
-        l1.next=merge(l1.next,l2);
-        return l1;
-    }else{
-        l2.next=merge(l1,l2.next);
-        return l2;
+class Solution {
+    public ListNode mergeKLists(ListNode[] lists) {
+        PriorityQueue<ListNode> minheap= new PriorityQueue<ListNode>((a,b)->(a.val-b.val));
+        for(ListNode list:lists){
+            if(list!=null)
+            minheap.add(list);
+        }
+        ListNode head=null;
+        ListNode tail=null;
+        while(!minheap.isEmpty()){
+            ListNode p =minheap.poll();
+            if(head==null){
+                head=p;
+                tail=p;
+            }else{
+                tail.next=p;
+                tail=p;
+            }
+            if(p.next!=null){
+                minheap.add(p.next);
+            }
+        }
+        return head;
+        
     }
-}
+    
 }
