欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

#leetcode刷题之路23-合并K个排序链表

程序员文章站 2022-04-08 19:16:00
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例:输入:[ 1->4->5, 1->3->4, 2->6]输出: 1->1->2->3->4->4->5->6 ......

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

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

 

 

#include <iostream>
#include <vector>
using  namespace std;
struct listnode {
    int val;
    listnode *next;
    listnode(int x) : val(x), next(null) {}
};

listnode* mergetwolists(listnode* l1, listnode* l2) {//合并两个有序链表
    listnode*temp;
    listnode*t;
    if(l1== nullptr) return l2;
    if(l2== nullptr) return l1;
    if(l1->val>l2->val)//把头节点值小的放前面
    {
        t=l1;l1=l2;l2=t;
    }
    listnode*head=l1;
    while(l2!= nullptr)
    {
        if(l1->next== nullptr)
        {
            l1->next=l2;
            return head;
        }
        else if(l1->val<=l2->val&&l1->next->val>=l2->val)
        {
            temp=l2->next;
            t=l1->next;
            l1->next=l2;
            l2->next=t;
            l1=l2;
            l2=temp;
        }
        else l1=l1->next;
    }
    return head;
}


listnode* mergeklists(vector<listnode*>& lists) {

    int len=lists.size();
    if(len==0) return nullptr;
    listnode* head=lists[0];
    if(len==1) return head;
    int n=0;
    while(n<len)//找到第一个不为空的链表,让头指针指向他
    {
        if(lists[n]!=nullptr)
        {head=lists[n];
            break;}
        else n++;
    }
    if(n==len) return nullptr;//全为空
    for(int i=n+1;i<len;i++)
    {
        if(lists[n]== nullptr) continue;//跳过空的
        head=mergetwolists(head,lists[i]);
    }
    return head;
}

int main() {
    std::cout << "hello, world!" << std::endl;
    return 0;
}