Merge k Sorted Lists

// Compare One-By-One (PQ)
public ListNode mergeKLists(ListNode[] lists) {
  if (lists == null || lists.length == 0) {
    return null;
  }
  ListNode dummy = new ListNode(-1);
  ListNode prev = dummy;

  PriorityQueue<ListNode> minPQ = new PriorityQueue<>((o1, o2) -> {
    return o1.val - o2.val;
  });

  // Init PQ
  for (int i = 0; i < lists.length; ++i) {
    if (lists[i] != null) {
      minPQ.offer(lists[i]);
    }
  }

  // Play with PQ
  while (minPQ.size() > 0) {
    ListNode curr = pq.poll();
    prev.next = curr;
    prev = prev.next; // update

    // you don't need to set curr.next as null since the last node is always be one of the last node of each list. Its next must be null.
    if (curr.next != null) {
      minPQ.offer(curr.next);
    }
  }
  
  return dummy.next;
}

#divide and conquer
class Solution {
    public ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(-1);
        ListNode temp = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                temp.next = left;
                temp = temp.next;
                left = left.next;
            } else {
                temp.next = right;
                temp = temp.next;
                right = right.next;
            }
        }
        while (left != null) {
            temp.next = left;
            temp = temp.next;
            left = left.next;
        }
        while (right != null) {
            temp.next = right;
            temp = temp.next;
            right = right.next;
        }
        return dummy.next;
    }
    
    public ListNode mergeSort(List<ListNode> lists, int start, int end) {
        if (start == end) {
            return lists.get(start);
        }
        int mid = start + (end - start) / 2;
        ListNode left = mergeSort(lists, start, mid);
        ListNode right = mergeSort(lists, mid + 1, end);
        return merge(left, right);
    }
    
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists.size() == 0) {
            return null;
        }
        return mergeSort(lists, 0, lists.size() - 1);
    }
}