23. Merge k Sorted Lists

Description

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

Solution

可以借助于21. Merge Two Sorted Lists，拥有了合并两个有序单链表的能力，合并k个有序链表自然手到擒来。
二分法递归调用，时间复杂度O(nlog(k))

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return this->mergeKSortedLists(lists, 0, lists.size() - 1);
    }

    ListNode* mergeKSortedLists(vector<ListNode*>& lists, int begin, int end) {
        if (lists.size() == 0 || begin > end) {
            return NULL;
        } else if (begin == end) {
            return lists[begin];
        } else if (end == begin + 1) {
            return this->mergeTwoLists(lists[begin], lists[end]);
        }
        int mid = (begin + end)/2;
        auto l1 = this->mergeKSortedLists(lists, begin, mid);
        auto l2 = this->mergeKSortedLists(lists, mid + 1, end);
        return this->mergeTwoLists(l1, l2);
    }

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        auto p = l1, q = l2;
        auto dummy = new ListNode(-1), pNode = dummy;
        while (p || q) {
            if (p == NULL) {
                pNode->next = q;
                return dummy->next;
            }
            if (q == NULL) {
                pNode->next = p;
                return dummy->next;
            }
            if (p->val < q->val) {
                pNode->next = p;
                p = p ->next;
            } else {
                pNode->next = q;
                q = q->next;
            }
            pNode = pNode->next;
        }
        return dummy->next;
    }
};