Merge

Merge sort

Merge K sorted list

• 3种解法

  • 用priorityQueue, 适合处理data stream大数据问题

  • top down merge sort 先局部有序，再整体有序, 首选

  • bottom up merge sort

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return mergeSolution(lists);
    }
    //Time: O(NlogK)
    //Space: O(K)
    private ListNode heapSolution(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> (a.val - b.val));
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.add(node);
            }
            
        }
        ListNode dummy = new ListNode(-1), head = dummy;
        while (!minHeap.isEmpty()) {
            ListNode cur = minHeap.poll();
            head.next = cur;
            if (cur.next != null) {
                minHeap.add(cur.next);
                cur.next = null;
            }
            head = head.next;
        }
        return dummy.next;
    }
    
    //Time: O(NLogK)
    //Space: O(1)
    private ListNode mergeSolution(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return mergeSort(lists, 0, lists.length - 1);
    }
    
    private ListNode mergeSort(ListNode[] lists, int begin, int end) {
        if (begin == end) return lists[begin];
        int mid = begin + (end - begin) / 2;
        ListNode first = mergeSort(lists, begin, mid);
        ListNode second = mergeSort(lists, mid + 1, end);
        return merge(first, second);
    }
    
    private ListNode merge(ListNode p, ListNode q) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (p != null && q != null) {
            if (p.val < q.val) {
                cur.next = p;
                p = p.next;
            } else {
                cur.next = q;
                q = q.next;
            }
            cur = cur.next;
        }
        while (p != null) {
            cur.next = p;
            p = p.next;
            cur = cur.next;
        }
        while (q != null) {
            cur.next = q;
            q = q.next;
            cur = cur.next;
        }
        return dummy.next;
    }
}