package com.fishercoder.solutions;

import com.fishercoder.common.classes.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 23. Merge k Sorted Lists
 *
 * Merge k sorted linked lists and return it as one sorted list.
 * Analyze and describe its complexity.*/

public class _23 {

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue((Comparator<ListNode>) (o1, o2) -> o1.val - o2.val);

        for (ListNode node : lists) {
            if (node != null) {
                heap.offer(node);
            }
        }

        ListNode pre = new ListNode(-1);
        ListNode temp = pre;
        while (!heap.isEmpty()) {
            ListNode curr = heap.poll();
            temp.next = new ListNode(curr.val);
            if (curr.next != null) {
                heap.offer(curr.next);
            }
            temp = temp.next;
        }
        return pre.next;
    }

}

@@ -302,17 +302,56 @@
 s _23 %7B%0A
-%0A
+    public static class Solution1 %7B%0A    
     publ
@@ -386,32 +386,36 @@
 Node%5B%5D lists) %7B%0A
+    
         Priority
@@ -517,16 +517,20 @@
         
+  
+  
 for (Lis
@@ -559,24 +559,28 @@
             
+    
 if (node != 
@@ -595,32 +595,36 @@
                 
+ 
+   
 heap.offer(node)
@@ -625,16 +625,20 @@
 (node);%0A
+    
         
@@ -651,19 +651,27 @@
         
-%7D%0A%0A
+    %7D%0A%0A    
         
@@ -703,32 +703,36 @@
 de(-1);%0A        
+    
 ListNode temp = 
@@ -744,16 +744,20 @@
         
+   
+ 
 while (!
@@ -770,24 +770,28 @@
 sEmpty()) %7B%0A
+    
             
@@ -827,24 +827,28 @@
             
+  
+  
 temp.next = 
@@ -879,24 +879,28 @@
             
+    
 if (curr.nex
@@ -920,32 +920,36 @@
                 
+ 
+   
 heap.offer(curr.
@@ -959,32 +959,36 @@
 t);%0A            
+    
 %7D%0A            te
@@ -981,24 +981,28 @@
             
+ 
+   
 temp = temp.
@@ -1003,24 +1003,28 @@
  temp.next;%0A
+    
         %7D%0A  
@@ -1029,16 +1029,20 @@
         
+    
 return p
@@ -1046,21 +1046,31 @@
 n pre.next;%0A
+        %7D%0A
     %7D%0A%0A%7D%0A

refactor 23