leetcode 23. 合并 K 个升序链表-526互联

题目链接：https://leetcode.cn/problems/merge-k-sorted-lists/

第一种写法，不断将未排序的链表插入到一个已经排序的链表中。
这样写的问题在于，当未排序的链表逐渐变的很大时，每插入一个新链表，都会来一次O(kn)，总时间复杂度为O(k²n)
我们可以通过分治，快速的消灭未排序链表个数，这样可以达到O(kn logk)

非分治写法：

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) {
            return nullptr;
        }

        ListNode* head = nullptr;
        int i = 0;
        while (i < lists.size() && !lists[i]) { i++; }
        if (i >= lists.size()) { return nullptr; }

        head = lists[i++];
        for (; i < lists.size(); ++i) {
            ListNode* p = lists[i];
            ListNode* phead = head;
            while (p) {
                if (p->val <= head->val) {
                    ListNode* tmp = p->next;
                    p->next = head;
                    head = p;
                    phead = head;
                    p = tmp;
                    continue;
                }
                while (phead->next && p->val > phead->next->val) {
                    phead = phead->next;
                }
                ListNode* tmp = p->next;
                p->next = phead->next;
                phead->next = p;
                p = tmp;
            }
        }
        return head;
    }

分治写法：
注意这一句 return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));，有点绕

    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a) || (!b)) return a ? a : b;
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr; 
                aPtr = aPtr->next;
            } else {
                tail->next = bPtr; 
                bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        tail->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }
    
    ListNode* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }