#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; }
上一篇: 被前男友分手两年了
下一篇: 逛商场看到个帅哥抱只超级可爱的小狗