【LeetCode】【数组归并】Merge k Sorted Lists

2021-06-18 02:03

阅读：686

标签：klist for amp sts 一个 NPU ret 归并 erase

描述

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

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

思路

借鉴Merge Two Sorted Lists的解决思路，对两个数组先进行排序，然后两两组合，排成一个序列。

将此视为一种迭代的分而治之的解决方案。

mergeTwoLists方法是一种递归的合并两个序列的方法

注意：

尽量不用erase方法，太耗时。

一些优化以避免vector.erase()

比如下述：

 while(lists.size() > 1){
        lists.push_back(mergeTwoLists(lists[0], lists[1]));
        lists.erase(lists.begin());
        lists.erase(lists.begin());
    }
    return lists.front();

改为使用指针方法遍历vector，最后取vector.back()

最终解决方案：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector& lists) {
        if(lists.empty()){
            return nullptr;
        }
        if(lists.size() == 1) return lists[0];
        int i = 0;
        while(i 1){
            lists.push_back(mergeTwoLists(lists[i], lists[i+1]));
            i += 2;
        }
        return lists.back();
    }
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr){
            return l2;
        }
        if(l2 == nullptr){
            return l1;
        }
        if(l1->val val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

【LeetCode】【数组归并】Merge k Sorted Lists

标签：klist for amp sts 一个 NPU ret 归并 erase

原文地址：https://www.cnblogs.com/ygh1229/p/9718627.html

上一篇：数组翻转（非reverse）

下一篇：使用java进行 AES 加密解密?

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【LeetCode】【数组归并】Merge k Sorted Lists
文章链接：http://soscw.com/essay/95282.html

亲，登录后才可以留言！

【LeetCode】【数组归并】Merge k Sorted Lists

描述

思路

注意：

评论

热门文章

推荐文章

最新文章

置顶文章