Merge k Sorted Lists

标签（空格分隔）： C++ 算法 LeetCode 链表

每日算法——leetcode系列

问题 Merge k Sorted Lists

Difficulty: Hard

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

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* mergeKLists(vector<ListNode*>& lists) {}};

翻译

合并k个有序链表

难度系数：困难

合并k个有序链表并返回合并后的有序链表。 分析并说明复杂度。

思路

有前面的Merge Two Sorted Lists， 这个题就变得简单了，k个可以每次把两个合并成一个，再把第三个跟刚合并的再合并，依次类推。
时间复杂度$Tn = O(n^2)$, 空间复杂度$O(1)$

上面的分析方法有点问题，如果总是合并成一个链表，会导致此链表很长，遍历时间会加倍，没有充分利用二分的优势， 所以得两两合并效率才高。

代码

class Solution {    public:    ListNode* mergeKLists(vector<ListNode*>& lists){        if (lists.empty()){return nullptr;        }        ListNode *p = lists[0];        // 会超时，必须先两两合并才可以//        while (lists.size() > 1) {//p = mergeTwoLists2(p, lists.back());//lists.pop_back();//        }    while (lists.size() > 1) {auto list1 = lists.back();lists.pop_back();auto list2 = lists.back();lists.pop_back();p =  mergeTwoLists2(list1, list2);lists.insert(lists.begin(), p);        }        return p;    }private:    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {        ListNode *p1 = l1,  *p2 = l2;        ListNode dummy(-1);        dummy.next = p1;        ListNode *tempLink = &dummy;    while(p1 != nullptr && p2 != nullptr) {if (p1->val < p2->val) {    tempLink = p1;    p1 = p1->next;} else {    tempLink->next = p2;    p2 = p2->next;    tempLink = tempLink->next;    tempLink->next = p1;}        }        if (p2 != nullptr) {tempLink->next = p2;        }    return dummy.next;    }ListNode* mergeTwoLists2(ListNode* l1, ListNode* l2) {        ListNode *p1 = l1,  *p2=l2;        ListNode dummy(-1);        dummy.next = nullptr;        ListNode *tempLink = &dummy;    while(p1 != nullptr && p2 != nullptr) {if (p1->val < p2->val) {    tempLink->next = p1;    p1 = p1->next;    tempLink = tempLink->next;} else {    tempLink->next = p2;    p2 = p2->next;    tempLink = tempLink->next;}        }        if (p2 != nullptr) {tempLink->next = p2;        } else if ( p1 != nullptr) {tempLink->next = p1;        }    return dummy.next;    }};