LeetCode: Merge k Sorted Lists

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Java:

public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(lists.size()==0) return null;
        PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){public int compare(ListNode a, ListNode b){return a.val>b.val?1:(a.val==b.val?0:-1);}});
        
        for(ListNode list:lists){
            if(list!=null) q.add(list);
        }
                
        ListNode head = new ListNode(0), prev = head;
        while(q.size()!=0){
            ListNode temp = q.poll();
            prev.next = temp;
            if(temp.next!=null) q.add(temp.next);
            prev = prev.next;
        }
        return head.next;
    }
}

C++:

class CompareListNode {
    public:
    bool operator()(ListNode *n1, ListNode *n2) // Returns true if t1 is earlier than t2
    {
       if (n1->val >= n2->val) 
        return true;
       else 
        return false;
    }
};
 
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        priority_queue<ListNode *, vector<ListNode *>, CompareListNode> q;
        for (const auto &list : lists) {
            if (list != NULL) {
                q.push(list);
            }
        }
        ListNode *output = NULL;
        ListNode *curr = output;
        while (q.size() > 0) {
            ListNode *temp = q.top();
            if (curr == NULL) {
                output = temp;
                curr = output;
            } else {
                curr->next = temp;
                curr = curr->next;
            }
            q.pop();
            if (temp->next != NULL) {
                q.push(temp->next);
            }
        }
        return output;
    }
};