首页 > 编程语言 > 详细

LeetCode23 合并k个排序链表

时间:2020-07-25 20:23:55      阅读:59      评论:0      收藏:0      [点我收藏+]

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

 

第一种方法,连续对链表做两两合并,时间复杂度和空间复杂度如下:

技术分享图片

 

 

 

第二种方法,归并法,每次合并相邻的两个链表

技术分享图片

 

第三种方法,优先队列。先把k个链表头压入,然后每次取出val最小的指针,然后压入下一个。

技术分享图片

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 
10 struct Status{
11     int val;
12     ListNode* ptr;
13     bool operator< (const Status &comp) const{
14         return val>comp.val;
15     }
16 };
17 
18 class Solution {
19 public:
20     ListNode* mergeKLists(vector<ListNode*>& lists) {
21         priority_queue<Status> q;
22         for(auto node:lists){
23             if(node!=nullptr)
24                 q.push({node->val,node});
25         }
26         ListNode head,*tail=&head;
27         while(!q.empty()){
28             auto temp=q.top();
29             q.pop();
30             if(temp.ptr->next!=nullptr)
31                 q.push({temp.ptr->next->val,temp.ptr->next});
32             tail->next=temp.ptr;
33             tail=tail->next;
34         }
35         return head.next;
36     }
37 };

 

LeetCode23 合并k个排序链表

原文:https://www.cnblogs.com/rookiez/p/13375967.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!