Merge k Sorted Lists

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

Analyze and describe its complexity.

Thoughts

此题有三种解法。 1. 用heap把每个元素存起来，然后再一个个吐出来。最好实现，每次插入和删除的时间复杂度为O(lgn),所以总时间复杂度O(nlgn) 2. 大merge sort, 挑整个大列表的中间的小列表作为中点，然后进行列表之间的合并，时间复杂度同普通merge sort, O(nlgn). 3. 两两合并。

Code

public class Solution {
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    public ListNode mergeKLists(List<ListNode> lists) {  
        return mergeSort(lists, 0, lists.size() - 1);
    }

    private ListNode mergeSort(List<ListNode> lists, int start, int end) {
        if (end == start) {
            return lists.get(end);
        } else if (end < start) {
            return null;
        }
        int mid = start + (end - start) / 2;
        ListNode left = mergeSort(lists, start, mid);
        ListNode right = mergeSort(lists, mid + 1, end);

        return merge(left, right);
    }

    private ListNode merge(ListNode A, ListNode B) {
        ListNode res = new ListNode(0), head = res; 
        while (A != null && B != null) {
            if (A.val < B.val) {
                head.next = A;
                A = A.next;
            } else {
                head.next = B;
                B = B.next;
            }
            head = head.next;
        } 
        if (A == null) {
            head.next = B;
        } else {
            head.next = A;
        }

        return res.next;
    }
}

Analysis

TC: O(nlgn)