[LeetCode]23. 合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

思路:

这是一道困难难度的题目。 想法很容易想到，既然是每个ListNode都是递增有序列表，那么只需要每轮遍历一次整个vector<ListNode*>中每个链表的头节点，选出最小的节点，然后拼接到暂存链表的尾部即可。停止条件也很直观，当vector中所有ListNode链表均访问到尾部即停止。

第二个想法来自于合并两个有序链表这道题。如果序链表成对合并，那么vector<ListNode*>中有k个链表的话，第一轮合并会把它变成k/2个，第m轮合并即可把链表数量减少到\( \frac{k}{2^{m}}\) 个。

AC代码:

//非常慢的头节点扫描版
/**
 * 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) {
        if(lists.empty())
            return nullptr;
        ListNode* Result = new ListNode(-1);
        ListNode* RPresent = Result;
        ListNode* temp = GetPresentSmallestNumber(lists);
        while(temp)
        {
            if(temp != nullptr)
            {
                RPresent->next = temp;
                RPresent = RPresent->next;
            }
            temp = GetPresentSmallestNumber(lists);
        }
        return Result->next;
    }
    ListNode* GetPresentSmallestNumber(vector<ListNode*>& lists)
    {
        ListNode* t_Result = nullptr;
        int t_Length = lists.size(), t_FinishCounter = 0;
        int t_minValue = std::numeric_limits<int>::max(), t_minIndex = 0;     
        for(int t_index = 0; t_index < t_Length; t_index++)
        {
            if(lists[t_index] != nullptr)
            {
                if(lists[t_index]->val < t_minValue)
                {
                    t_minValue = lists[t_index]->val;
                    t_minIndex = t_index;
                }
            }
            else
            {
                t_FinishCounter++;
            }
        }
        if(t_Length == t_FinishCounter)
        {
            t_Result = nullptr;
        }
        else
        {
            t_Result = lists[t_minIndex];
            lists[t_minIndex] = lists[t_minIndex]->next;
            t_Result->next = nullptr;
        }
        return t_Result;
    }
};

双有序链表合并直接用了我以前写的这篇文章的代码。

//快一些的链表两两合并版
/**
 * 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) {
        if(lists.size()< 1)
            return nullptr;
        if(lists.size()< 2)
            return lists[0];
        vector<ListNode*> tempResult;
        while(lists.size() > 1)
        {
            for(unsigned int t_index = 0; (t_index < lists.size()) && (t_index + 1 < lists.size()); t_index += 2)
            {
                tempResult.push_back(mergeTwoLists(lists[t_index], lists[t_index + 1]));
            }
            if(lists.size() % 2 == 1)
            {
                tempResult.push_back(lists.back());
            }
            lists = tempResult;
            tempResult.clear();                         
        }
        return lists[0];
    }
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr) 
        {
            if(l2 == nullptr) 
                return nullptr;
            else
                return l2;
        }
        else
        {
            if(l2 == nullptr) 
                return l1;
        }
        //l1 != nullptr, l2 != nullptr
        ListNode dummyHeadNode(-10000);
        dummyHeadNode.next = l1;
        ListNode* cursor1 = &dummyHeadNode,* cursor2 = l2;
        while(cursor1 != nullptr && cursor1->next != nullptr && cursor2 != nullptr)
        {
            if(cursor1->val <= cursor2->val && cursor1->next->val > cursor2->val)
            {
                ListNode* temp = cursor2;
                cursor2 = cursor2->next;
                temp->next = cursor1->next;
                cursor1->next = temp;
            }
            cursor1 = cursor1->next;
        }
        if(cursor1->next == nullptr && cursor2 != nullptr)
            cursor1->next = cursor2;
        return dummyHeadNode.next;
    }
};