题解 | #合并k个已排序的链表#

合并k个已排序的链表

http://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {//对于两个链表的合并
        ListNode* p1 = pHead1,*p2 = pHead2;
        if(p1 == nullptr) return p2;
        if(p2 == nullptr) return p1;
        ListNode* now = new ListNode(-1);
        ListNode* dumb = now;
        while(p1 && p2){
            if(p1->val<p2->val){
                now->next = p1;
                now = now->next;
                p1 = p1->next;
            }
            else{
                now->next = p2;
                now = now->next;
                p2 = p2->next;
            }
        }
        if(p1) now->next = p1;
        if(p2) now->next = p2;
        return dumb->next;
    }
    ListNode* mergelist(vector<ListNode*>& lists,int l,int r){//分治算法
        if(l==r){//终止条件:l==r,l>r两个
            return lists[l];
        }
        if(l>r) return nullptr;
        int mid = l+((r-l)>>1);
        return Merge(mergelist(lists, l, mid),mergelist(lists, mid+1, r));之后不断分开就好了
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        return mergelist(lists, 0, lists.size()-1);//分治算法,注意输入条件
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 14:45
bg是二本双一流硕,目标是Java后端开发岗,投暑期实习0大厂面试,只有极少的大厂测开,可能投的晚加上简历太烂加上0实习?求大佬们给个建议
程序员小白条:别去小厂,初创或者外包,尽量去中小,100-499和500-999,专门做互联网产品的,有公司自研的平台和封装的工具等等,去学习一些业务相关的,比如抽奖,积分兑换,SSO认证,风控,零售等等,目标 Java 后端开发吗?你要不考虑直接走大厂测开?如果技术不行的话,有面试你也很难过的
实习,不懂就问
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 15:39
希望奇迹发生的布莱克...:真的是 现在卷实习就是没苦硬吃
点赞 评论 收藏
分享
点赞 评论 收藏
分享
程序员饺子:正常 我沟通了200多个 15个要简历 面试2个 全投的成都的小厂。很多看我是27直接不会了😅
点赞 评论 收藏
分享
昨天 11:33
江南大学 Java
已经在暑假实习了&nbsp;,没有明确说有hc,纠结实习到八月份会不会有点影响秋招毕竟感觉今年好多提前批
程序员小白条:92的话准备提前批,其他没必要,没面试机会的,而且你要准备充分,尤其八股和算法题
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务