Merge k Sorted Lists 104

Question

Merge k sorted linked lists and return it as one sorted list.

Analyze and describe its complexity.

Example

Given lists:

[ 2->4->null, null, -1->null ],

return -1->2->4->null.

Solution

这道题可以用3种方法解。

第一种方法：D&C。总共有n条sorted list，将前n／2条进行合并，将后n／2条进行合并，再将左右进行合并。

第二种方法：merge 2 by 2。和第一种方法类似，两条两条merge，比如1-2，3-4，。。。，将merge完的加入到新的lists中。如果n为奇数，最后一条没法和下一条merge，直接加入到新lists中。一直这样两两merge直到只剩下1条为止。

第三种方法：用PriorityQueue(heap)实现。将每个list的开头node加入pq中，根据node的value大小从小到大排序。然后将队头元素（最小元素）出队，并将该元素的next元素入队。一直重复，直到队列为空为止。

代码如下：

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    //version1: D&C
    /*
    private ListNode merge(ListNode left, ListNode right){
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;

        while(left != null && right != null){
            if(left.val < right.val){
                head.next = left;
                left = left.next;
            }else{
                head.next = right;
                right = right.next;
            }
            head = head.next;
        }

        if(left != null){
            head.next = left;
        }

        if(right != null){
            head.next = right;
        }

        return dummy.next;
    }

    public ListNode mergeKLists(List<ListNode> lists) {  
        // write your code here
        if(lists == null || lists.size() == 0){
            return null;
        }

        if(lists.size() == 1){
            return lists.get(0);
        }

        int size = lists.size();
        List<ListNode> leftLists = new ArrayList<ListNode>();
        List<ListNode> rightLists = new ArrayList<ListNode>();

        for(int i = 0; i < size; i++){
            if(i < size/2){
                leftLists.add(lists.get(i));
            }else{
                rightLists.add(lists.get(i));
            }
        }

        ListNode left = mergeKLists(leftLists);
        ListNode right = mergeKLists(rightLists);

        return merge(left, right);
    }*/


    /*
    //version2: merge 2 by 2
    public ListNode mergeKLists(List<ListNode> lists) {  
        // write your code here
        if(lists == null || lists.size() == 0){
            return null;
        }

        while(lists.size() > 1){
            List<ListNode> newLists = new ArrayList<ListNode>();
            for(int i = 0; i < lists.size() - 1; i++){
                if(i % 2 == 0){
                    ListNode node = merge(lists.get(i), lists.get(i + 1));
                    newLists.add(node);
                }
            }
            if(lists.size() % 2 != 0){
                newLists.add(lists.get(lists.size() - 1));
            }
            lists = newLists;
        }

        return lists.get(0);
    }

    private ListNode merge(ListNode left, ListNode right){
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;

        while(left != null && right != null){
            if(left.val < right.val){
                head.next = left;
                left = left.next;
            }else{
                head.next = right;
                right = right.next;
            }

            head = head.next;
        }

        if(left != null){
            head.next = left;
        }

        if(right != null){
            head.next = right;
        }

        return dummy.next;
    }


    */
    //ListNode[] heapArray;
    //heapsort version
    private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>() {
        public int compare(ListNode left, ListNode right) {
            // if (left == null) {
            //     return 1;
            // } else if (right == null) {
            //     return -1;
            // }
            return left.val - right.val;
        }
    };

    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }

        Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), ListNodeComparator);
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null) {
                heap.add(lists.get(i));
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            ListNode head = heap.poll();
            tail.next = head;
            tail = head;
            if (head.next != null) {
                heap.add(head.next);
            }
        }
        return dummy.next;
    }
}