Cacher is the code snippet organizer for pro developers

/*
⭐️⭐️⭐️
Time complexity:
  O(Nlogk) where k is the number of linked lists.
  
Space complexity:
  O(n) Creating a new linked list costs O(n) space.
  O(k) The code above present applies in-place method which cost O(1) space. 

*/

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        
        Comparator<ListNode> cmp;
        cmp = new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1,ListNode o2){
              /*
                if (o1.val < o2.val)
                    return -1;
                else if (o1.val == o2.val)
                    return 0;
                else 
                    return 1;
              */
              return o1.val - o2.val;
            }
        };
        
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(cmp);
        
      /*        
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1,ListNode o2){
              return o1.val - o2.val;
            }
        });
      */
        
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        
        for (ListNode node : lists) {
            if (node != null) {
                queue.add(node);
            }
        }
            
        while(!queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
            if (cur.next != null) {
                queue.add(cur.next);
            }
        }
        
        return dummy.next;
    }
}

/*
⭐️⭐️
Time is O(nlogk), merge takes O(n) time and partition takes O(logk) time
*/

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return sort(lists, 0, lists.length - 1);
    }
    
    private ListNode sort(ListNode[] lists, int lo, int hi) {
        if (lo >= hi) return lists[lo];
        int mid = lo + (hi - lo) / 2;
        ListNode l1 = sort(lists, lo, mid);
        ListNode l2 = sort(lists, mid + 1, hi);
        return mergeTwoLists(l1, l2);
    }
    
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

/*
⭐️
Time:  O(kn)
Space: O(n)
*/


class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> l = new ArrayList<Integer>();
        ListNode head = new ListNode(0);
        ListNode cur = head;
        int min_index = 0;
        
        while(true) {
            boolean isVisitedAll = true;
            int min = Integer.MAX_VALUE;
            for(int i = 0; i < lists.length; i++) {
                if(lists[i] != null) {
                    isVisitedAll = false;
                    if(lists[i].val < min) {
                        min = lists[i].val;
                        min_index = i;
                        //lists[min_index] = lists[min_index].next; 不能写到这里因为当前这个不一定是最小的
                    }
                }
            }
            
            if(isVisitedAll) {
                break;
            }
            
            ListNode newNode = new ListNode(min);
            cur.next = newNode;
            cur = cur.next;
            lists[min_index] = lists[min_index].next;  
        }
        
        cur.next = null;
        return head.next;
    }
}

/*
Time:  O(nlogn)
Space: O(n)
*/

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> l = new ArrayList<Integer>();
        for (ListNode ln : lists) {
            while (ln != null) {
                l.add(ln.val);
                ln = ln.next;
            }
        }

        Collections.sort(l);
        
        ListNode head = new ListNode(0);
        ListNode h = head;
        for (int i : l) {
            ListNode t = new ListNode(i);
            h.next = t;
            h = h.next;
        }
        h.next = null;
        return head.next;
    }
}

class Solution {
  public ListNode mergeKLists(ListNode[] lists) {
      if(lists.length==1){
          return lists[0];
      }
      if(lists.length==0){
          return null;
      }
      ListNode head = mergeTwoLists(lists[0],lists[1]);
      for (int i = 2; i < lists.length; i++) {
          head = mergeTwoLists(head,lists[i]);
      }
      return head;
  }
  
  
  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
      ListNode h = new ListNode(0);
      ListNode ans=h;
      while (l1 != null && l2 != null) {
          if (l1.val < l2.val) {
              h.next = l1;
              h = h.next;
              l1 = l1.next;
          } else {
              h.next = l2;
              h = h.next;
              l2 = l2.next;
          }
      }
      if(l1==null){
          h.next=l2;
      }
      if(l2==null){
          h.next=l1;
      } 
      
      return ans.next;
  }
}