[LeetCode C实现]23. Merge k sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
实现思路：由于在LeetCode C实现 21. Merge two sorted Lists中我们已经完成了两个有序链表的合并，所以k个有序链表的合并可以依次合并，经过k-1次合并成一个链表。
实现代码如下：
方法一：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) 
{
    if(NULL == l1 && NULL != l2)
        return l2;
    else if(NULL == l2 && NULL != l1)
        return l1;
    else if (NULL == l1 && NULL == l2)
        return NULL;
    
    struct ListNode *head = NULL;
    /*返回新链表的头结点*/
    struct ListNode *ret = NULL;

    /*确定链表头*/
    if(l1->val < l2->val)
    {
        head = l1;
        l1 = l1->next;
    }
    else
    {
        head = l2;
        l2 = l2->next;
    }
    
    /*保存链表头*/
    ret = head;
    
    while(l1 &&l2)
    {
        if(l1->val >l2->val)
        {
            head->next = l2;
            l2 = l2->next;
        }
        else
        {
            head->next = l1;
            l1 = l1->next;
        }
        /*新插入的结点next置NULL*/
        head->next->next = NULL;
        head = head->next;
            
    }
    
    if(l1)
        head->next = l1;
    else if (l2)
        head->next = l2;
    
    return ret;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) 
{
    /*k小于2，返回第一个链表*/
     if(listsSize < 2)
        return lists[0];
    /*合并两个链表*/
    struct ListNode * cmp = mergeTwoLists(lists[0],lists[1]);
    for(int i = 2;i < listsSize;i++)
    {
        cmp = mergeTwoLists(cmp,lists[i]);
    }
    
    return cmp;
    
}

方法二：分治法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) 
{
    if(NULL == l1 && NULL != l2)
        return l2;
    else if(NULL == l2 && NULL != l1)
        return l1;
    else if (NULL == l1 && NULL == l2)
        return NULL;
    
    struct ListNode *head = NULL;
    /*返回新链表的头结点*/
    struct ListNode *ret = NULL;

    /*确定链表头*/
    if(l1->val < l2->val)
    {
        head = l1;
        l1 = l1->next;
    }
    else
    {
        head = l2;
        l2 = l2->next;
    }
    
    /*保存链表头*/
    ret = head;
    
    while(l1 &&l2)
    {
        if(l1->val >l2->val)
        {
            head->next = l2;
            l2 = l2->next;
        }
        else
        {
            head->next = l1;
            l1 = l1->next;
        }
        /*新插入的结点next置NULL*/
        head->next->next = NULL;
        head = head->next;
            
    }
    
    if(l1)
        head->next = l1;
    else if (l2)
        head->next = l2;
    
    return ret;
}

struct ListNode* merge(struct ListNode** lists, int start,int end) 
{
    if(start > end)
        return NULL;
    if(start == end)
        return lists[start];
    
    int mid = (start + end) / 2;
    struct ListNode* left = merge(lists,start,mid);
    struct ListNode* right = merge(lists,mid + 1,end);
    return mergeTwoLists(left,right);
    
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) 
{
    return merge(lists,0,listsSize-1); 
}

2021.06.12更新笔记

C++两两合并实现:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* dummy = nullptr;
        for(int i = 0;i < lists.size();i++)
        {
            dummy = merge2Lists(dummy,lists[i]);
        }
        return dummy;
    }
private:
    ListNode* merge2Lists(ListNode* l1,ListNode* l2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        while(l1 && l2)
        {
            if(l1->val < l2->val)
            {
                p->next = l1;
                l1 = l1->next;
            }else{
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        if(l1) p->next = l1;
        if(l2) p->next = l2;
        ListNode* newhead = dummy->next;
        delete dummy;
        return newhead;
    }
};

运行效率较低160 ms 仅击败29.10%的用户。
```

执行用时：160 ms, 在所有 C++ 提交中击败了29.10%的用户
内存消耗：13.1 MB, 在所有 C++ 提交中击败了40.93%的用户

#####分治法

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
/
class Solution {
public:
ListNode mergeKLists(vector& lists) {
return merge(lists,0,lists.size()-1);
}
private:
ListNode* merge(vector& lists,int l,int r) {
if(l == r) return lists[l];
if(l > r) return nullptr;
int mid = l + (r - l)/2;
return merge2Lists(merge(lists,l,mid),merge(lists,mid+1,r));
}

ListNode* merge2Lists(ListNode* l1,ListNode* l2) {
    ListNode* dummy = new ListNode(-1);
    ListNode* p = dummy;
    while(l1 && l2)
    {
        if(l1->val < l2->val)
        {
            p->next = l1;
            l1 = l1->next;
        }else{
            p->next = l2;
            l2 = l2->next;
        }
        p = p->next;
    }
    if(l1) p->next = l1;
    if(l2) p->next = l2;
    ListNode* newhead = dummy->next;
    delete dummy;
    return newhead;
}

};

运行效率:

执行用时：36 ms, 在所有 C++ 提交中击败了45.24%的用户
内存消耗：23.7 MB, 在所有 C++ 提交中击败了5.32%的用户

#####优先队列完美解法

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
private:
struct Status {
int val;
ListNode ptr;
bool operator < (const Status &rhs) const {
return this->val > rhs.val;
}
};
priority_queue q;
public:
ListNode mergeKLists(vector& lists) {
for(auto head:lists)
{
if(!head) continue;
q.push({head->val,head});
}

    ListNode* dummy = new ListNode(-1);
    ListNode* p = dummy;
    while(!q.empty())
    {
        auto elem = q.top();
        q.pop();

        ListNode* node = elem.ptr;
        p->next = node;
        p = p->next;
        //链表还有next结点,添加next到优先队列
        if(node && node->next)
            q.push({node->next->val,node->next});
    }
    return dummy->next;
}

};

运行结果:

执行用时：20 ms, 在所有 C++ 提交中击败了97.20%的用户
内存消耗：13.2 MB, 在所有 C++ 提交中击败了27.53%的用户
```

52coder

[LeetCode C实现]23. Merge k sorted Lists

C++两两合并实现: