[LeetCode] Merge k Sorted Lists

Problem:

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

Code V1 ( Time Limit Exceeded):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0)
            return null;
        
        ListNode r = new ListNode(0);
        ListNode result = r;
        
        while (isEmpty(lists) == false) {
            Stack<Integer> s = new Stack<Integer>();
            for (int i = 0; i < lists.size(); i++) {
                if (lists.get(i) == null)
                    continue;
                if (s.empty() || s.peek() > lists.get(i).val) {
                    s.push(lists.get(i).val);
                    lists.set(i, lists.get(i).next);
                }
            }

            while (s.empty() == false) {
                r.next = new ListNode(s.pop());
                r = r.next;
            }
        }
        
        return result.next;
        
    }
    
    public boolean isEmpty(ArrayList<ListNode> lists) {
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null)
                return false;
        }
        return true;

    }

}

Code V2 (Memory Limit Exceeded):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0)
            return null;
        
        ListNode r = new ListNode(0);
        ListNode result = r;
        
        while (isEmpty(lists) == false) {
            Stack<Integer> s = new Stack<Integer>();
            for (int i = 0; i < lists.size(); i++) {
                if (lists.get(i) == null)
                    continue;
                if (s.empty() || s.peek() > lists.get(i).val) {
                    s.push(lists.get(i).val);
                    lists.set(i, lists.get(i).next);
                }
            }

            while (s.empty() == false) {
                r.next = new ListNode(s.pop());
                r = r.next;
            }
        }
        
        return result.next;
        
    }
    
    public boolean isEmpty(ArrayList<ListNode> lists) {
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null)
                return false;
        }
        return true;

    }

}

Code V3 (Accepted):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        
        PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(100, new ListNodeComparator());
        for (int i = 0; i < lists.length; i++) {
            ListNode p = lists[i];
            if (p != null) {
                q.add(p);
            }
        }
        
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while (q.size() != 0) {
            ListNode node = q.poll();
            if (node.next != null) {
                q.add(node.next);
            }
            p.next = node;
            p = p.next;
        }
        
        return dummy.next;
    }
}

class ListNodeComparator implements Comparator<ListNode> {
  public int compare(ListNode n1, ListNode n2) {
    return n1.val - n2.val;
  }
}