使用 oh-my-zsh

23、 合并K个排序链表

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

示例:

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

C++ 基础方法两两合并

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* p1,ListNode* p2) {
        //  创建新的头节点
        ListNode* head = new ListNode(0);        
        ListNode* p = head;
        // 循环合并
        while (p1 != nullptr && p2 != nullptr) {
            if (p1->val <= p2->val){
                p->next = p1;
                p1 = p1->next;
            } else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        // 合并剩余部分
        if  (p1 != nullptr) {
            p->next = p1;
        }else if (p2 != nullptr){
            p->next = p2;
        }
        ListNode* t = head->next;
        delete head;
        return t;
    }
    // 两两归并
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return nullptr;
        
        ListNode* head = lists[0];
        for (int i = 1;i < lists.size(); ++i) {
           head = merge(head,lists[i]);
        }
        
        return head;
    }
};

C++ 基础方法两两合并优化，二分归并思想

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* p1,ListNode* p2) {
        //  创建新的头节点
        ListNode* head = new ListNode(0);        
        ListNode* p = head;
        // 循环合并
        while (p1 != nullptr && p2 != nullptr) {
            if (p1->val <= p2->val){
                p->next = p1;
                p1 = p1->next;
            } else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        // 合并剩余部分
        if  (p1 != nullptr) {
            p->next = p1;
        }else if (p2 != nullptr){
            p->next = p2;
        } else {
            p->next = nullptr;
        }
        ListNode* t = head->next;
        delete head;
        return t;
    }
    // 两两递归归并
    ListNode* mergeKListsCore(vector<ListNode*>& lists,int l,int r) {
        if (l == r -1) {
            return merge(lists[l],lists[r]);
        } else if (l >= r) {
             return lists[l];// 可能会出先单个链表
        }
        int mid = (l+r)>>1;
        ListNode* t1 = mergeKListsCore(lists,l,mid);
        ListNode* t2 = mergeKListsCore(lists,mid + 1,r);
    
        return merge(t1,t2);
    }
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int len = lists.size();
        if (len == 1) return lists[0];
        if (len >= 2) {
            return mergeKListsCore(lists,0,len - 1);
        }
        return nullptr;
    }
};

一位小伙伴的分治思想的精简C++实现

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists, int begin, int end) {
        if (end < begin) return NULL;
        if (end == begin) return lists[begin];

        int mid = (begin + end) / 2;
        auto p1 = mergeKLists(lists, begin, mid);
        auto p2 = mergeKLists(lists, mid + 1, end);

        ListNode head(0);
        ListNode* cur = &head;
        while (p1 && p2) {
            if (p1->val < p2->val) {
                cur->next = p1;
                p1 = p1->next;
            } else {
                cur->next = p2;
                p2 = p2->next;
            }
            cur = cur->next;
        }

        if (p1) cur->next = p1;
        else if (p2) cur->next = p2;
        return head.next;
    }

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

// 作者：dpapa
// 链接：https://leetcode-cn.com/problems/two-sum/solution/c-gui-bing-shi-xian-by-dpapa/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

一位小伙伴的分治思想的精简C实现

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
    struct ListNode head;
    struct ListNode  *p, *q;

    if (!l1) {
        return l2;
    }

    if (!l2) {
        return l1;
    }

    /* 建立新的头结点 指向L1 */
    head.next = l1;
    l1 = &head;
 
    /* 遍历l2节点 */
    while (l2) {
        p = l1->next;
        q = l2->next;

        if (!l1->next) {
            l1->next = l2;
            break;
        }
  
        if (p->val >= l2->val) {
            l1->next = l2;
            l2->next = p;
            l2 = q;
        }

        l1 = l1->next;
    }
    return head.next;
}

struct ListNode* _mergeKLists(struct ListNode** lists, int listsSize)
{
    int count;
    struct ListNode* l1, *l2;
    count = listsSize;

    if (count == 0) {
        return NULL;
    } else if (count == 1) {
        return lists[0];
    } else if (count == 2) {
        return mergeTwoLists(lists[0], lists[1]);
    }
 
    l1 = _mergeKLists(&lists[0], (count+1)/2);
    l2 = _mergeKLists(&lists[(count+1)/2], count - (count+1)/2);
  
    return mergeTwoLists(l1, l2);
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{  
    return _mergeKLists(lists, listsSize);
}

// 作者：wangyuanzhengbighead
// 链接：https://leetcode-cn.com/problems/two-sum/solution/cshi-xian-nlgnxiao-lu-chao-guo-90-by-wangyuanzheng/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

一位小伙伴的简单暴力解法，问题转化思想

ListNode* mergeKLists(vector<ListNode*>& lists) {
    // 将链表加入到动态数组中
    vector<ListNode*> longList;
    for (ListNode* start:lists){
        ListNode* ptr = start;
        while (ptr != NULL){
            longList.push_back(ptr);
            ptr = ptr->next;
        }
    }
    // 排序
    std::sort(longList.begin(),longList.end(),[](auto x,auto y){return ((x->val) < (y->val));});
    // 将节点连接起来
    if (longList.size() ==0){return NULL;}
    for (size_t i=0;i<longList.size()-1;i++){
        longList[i]->next = longList[i+1];
    }
    longList[longList.size()-1]->next = NULL;
    return longList[0];
}

// 作者：w5LCyMOoza
// 链接：https://leetcode-cn.com/problems/two-sum/solution/chao-jian-dan-suan-fa-stdsortgao-ding-by-w5lcymooz/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com