专栏首页书山有路勤为径k个排序链表的合并

k个排序链表的合并

LeetCode 23. Merge k Sorted Lists 已知k个已排序链表头节点指针,将这k个链表合并,合并后仍为有序的,返 回合并后的头节点。

思考与分析

最普通的方法,k个链表按顺序合并k-1次,暴力的进行合并。 设有k个链表,平均每个链表有n个节点,时间复杂度: (n+n)+(2n+n)+((k-1)n+n) = (1+2+...+k-1)n +(k-1)n =(1+2+...+k)n-n=(k^2+k-1)/2 * n = O(k^2*n)

是否与更好的方法?

方法1

将kn个节点放到vector中,再将vector排序,再将节点顺序相连。 设有k个链表,平均每个链表有n个节点,时间复杂度: kNlogkN + kN = O(kN*logkN) (比如k=100, n = 10000) logkN = 20, k = 100

#include<vector>
#include<algorithm>
bool cop(const ListNode *a, const ListNode *b){
    return a->val < b-> val;
}
int main(){
    ListNode a(3);
    ListNode b(2);
    ListNode c(5);
    ListNode d(0);
    std::vector<ListNode *> node_vec;
    node_vec.push_back(&a);
    node_vec.push_back(&b);
    node_vec.push_back(&c);
    node_vec.push_back(&d);
    std::sort(node_vec.begin(), node_vec.end(),cmp);
    for(int i = 0; i < node_vec.size(); i++){
        printf("%d\n",node_vec[i]->val);
    }
    return 0;
}
#include<vector>
#include<algorithm>
bool cmp(const ListNode *a, const ListNode *b){
    return a->val < b->val;
}
class Solution{
public:
    ListNode * mergeKList(std::vector<ListNode*>& lists){
    std::vector<ListNode *>node_vec;
        for(int i = 0; i < lists.size();i++){
            ListNode *head = list[i];
            while(head){
                node_vec.push_back(head);
                head = head->next;
        }
        if( node_vec.size() ==0){
           return NULL;
        }
        std::sort(node_vec.begin(),node_vec.end(),cmp);
        for(int i =1; i < node_vec.size(); i++){
            node_vec[i-1]->next = node_vec[i];
        }
        node_vec[node_vec.size()-1]->next = NULL;
        return node_vec[0];

    }
}
};
方法二 分制归并

对k个链表使用分制的思想,两两进行合并。 设有k个链表,平均每个链表有n个节点,时间复杂度: 第1轮,进行k/2次,每次处理2n个数字;第2轮,进行k/4次,每次处理4n个数字;...; 最后一次,进行k/(2logk)次,每次处理2logkN个值。 2Nk/2 + 4N * k/4 + 8N * k/8 +...+2^logk * N * k/(2^logk) =Nk + Nk +...+Nk = O(kNlogk)

ListNode *mergeKList(std::vector<ListNode*> &lists){
    if lists.size() == 0){
        return NULL;
    }
    if(lists.size() == 1){
        return list[0];//如果只有一个list,直接返回头节点
    }
    if(lists.size() == 2){
        return mergeTwoLists(lists[0],lists[1]);
    }
    int mid = lists.size() / 2;
    std::vector<ListNode *> sub1_lists;
    std::vector<ListNode*> sub2_lists;
    for(int i= 0; i < mid ; i++){
        sub1_lists.push_back(lists[i]);
    }
    for(int i = mid; i< lists.size();i++)
{
        sub2_lists.push_back(lists[i]);
    }
    ListNode * l1 = mergeKLists(sub1_lists);
    ListNode *l2= mergeKLists(sub2_lists);
    return mergeTwoList(l1,l2);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 二叉查找树编码与解码

    LeetCode 449 给定一个二叉查找树,实现对该二叉查找树编码与解码功能。编码即将二叉查找树转为字符串,解码即将字符串转为二叉查找树。不限制使用何种编码...

    小飞侠xp
  • 排序数组转换为二叉查找树

    已知一个排序的数组,将该数组转换为一个高度平衡的二叉查找树。 平衡的定义: 二叉查找树中,任意节点的两颗子树高度差不超过1. LeetCode 108

    小飞侠xp
  • 分治算法之归并排序

    分治算法: 将一个规模为N的问题分解为K个规模较小的子问题,这些子问题互相独立且与原问题性质相同。求出子问题的解后进行合并,就可得到原问题的解。

    小飞侠xp
  • 极限黑客破解:低温环境下读取Android加密数据

    背景 德国Erlangen大学研究人员找到了一种获取Android手机加密数据的新方法,利用“冷启动攻击”方式可以能从被锁定的Android手机中提取出信息。这...

    FB客服
  • iOS10凌晨1点发布,小源带你一起升级体验过程

    梁源
  • 耽误你的十分钟,让MVVM原理还给你

    众所周知当下是MVVM盛行的时代,从早期的Angular到现在的React和Vue,再从最初的三分天下到现在的两虎相争。

    Nealyang
  • Sentinel基于滑动窗口的流量统计【源码笔记】

    1.StatisticSlot主要职责是流量统计(为后面插槽链的流控和降级做准备),这些流量是如何统计出来的? 2.统计出来的流量在流控中是如何使用的?

    瓜农老梁
  • 用户名和密码校验程序

    skylark
  • 这款无人机的士,可以在没油的时候把你“弹”出去

    镁客网
  • 【JS】508- MVVM原理介绍

    今天花上 10 分钟,针对 MVVM 这个面试必考点,简简单单的来给大家划一下重难点

    pingan8787

扫码关注云+社区

领取腾讯云代金券