合并K个有序链表

题目描述
合并 k 个已排序的链表并将其作为一个已排序的链表返回。分析并描述其复杂度。

解法

    ListNode *mergeTwoLists(ListNode* a, ListNode* b) {
        if ( !a || !b ) return a? a: b;
        ListNode dummy(0);
        ListNode* tail = &dummy, *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 dummy.next;
    }
    //解法1：顺序合并
    // 时间:O(k*k*n) 空间O(1)
    /*
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode* ans = nullptr;
        for (int i = 0; i < lists.size(); i++) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
    */

    //解法2: 分治合并
    //时间O(k*n*logk) 空间O(logk)
     ListNode *merge(vector<ListNode *> &lists, int s, int e) {
         // 终止条件
         if (s > e) return nullptr;
         if (s == e) return lists[s]; //处理到了最基本元素，直接返回


         // 分
         int mid = (s + e)/2;
         ListNode* left = merge(lists, s, mid);
         ListNode* right = merge(lists, mid + 1, e);

         //合
         ListNode* all = mergeTwoLists(left, right);
         return all;
     }

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