Thursday, July 24, 2014

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        
        Queue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(), ListCom);
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null) {
                queue.offer(lists.get(i));   
            }
        }
        
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while (!queue.isEmpty()) {
            ListNode cur = queue.poll();
            head.next = cur;
            if (cur.next != null) {
                queue.offer(cur.next);
            }
            head = head.next;
        }
        return dummy.next;
    }
    
    private Comparator<ListNode> ListCom = new Comparator<ListNode>() {
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }  
    };
}

No comments:

Post a Comment