lintcode-104-合并k个排序链表
2024-08-28 21:05:28
104-合并k个排序链表
合并k个排序链表，并且返回合并后的排序链表。尝试分析和描述其复杂度。
样例
给出3个排序链表[2->4->null,null,-1->null]，返回 -1->2->4->null
标签
链表 分治法 堆 优先队列 优步 谷歌 推特 领英 爱彼迎 脸书
方法一（最简单，但效率不高）
每次从当前K个链表中，选取值最小的节点，加入已排序链表中
code
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
ListNode *mergeKLists(vector<ListNode *> &lists) {
// write your code here
ListNode * newHead = new ListNode(-1);
ListNode * current = newHead;
while(!isAllListEmpty(lists)) {
current->next = findMin(lists);
current = current->next;
}
return newHead->next;
}
bool isAllListEmpty(vector<ListNode *> &lists) {
for(int i=0; i<lists.size(); i++) {
if(lists[i] != NULL) {
return false;
}
}
return true;
}
ListNode *findMin(vector<ListNode *> &lists) {
int minValue = 0x7FFFFFFF;
int minIndex = 0;
ListNode * result = NULL;
for(int i=0; i<lists.size(); i++) {
if(lists[i] != NULL && lists[i]->val < minValue) {
minValue = lists[i]->val;
result = lists[i];
minIndex = i;
}
}
lists[minIndex] = lists[minIndex]->next;
return result;
}
};
方法二（使用最小堆）
方法一的时间消耗主要体现于在 k 个链表中寻找最小值，每次寻找最小值都需要 O(k) 的时间复杂度，所以可以采用最小堆，将 k 个链表的表头放入堆中，它们会自动排好序。然后取出堆顶元素加入已排序链表，把取出元素的下一个元素再加入堆中。以此类推，直至堆空。
code
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
struct cmp {
bool operator () (ListNode *a, ListNode *b) {
return a->val > b->val;
}
};
ListNode *mergeKLists(vector<ListNode *> &lists) {
// write your code here
priority_queue<ListNode*, vector<ListNode*>, cmp> minHeap;
for(int i=0; i<lists.size(); i++) {
if(lists[i] != NULL) {
minHeap.push(lists[i]);
}
}
ListNode *newHead = NULL, *current = NULL, *temp = NULL;
while (!minHeap.empty()) {
temp = minHeap.top();
minHeap.pop();
if (current == NULL) {
newHead = temp;
}
else {
current->next = temp;
}
current = temp;
if (temp->next != NULL) {
minHeap.push(temp->next);
}
}
return newHead;
}
};
最新文章
- 《Entity Framework 6 Recipes》中文翻译系列 (37) ------ 第六章 继承与建模高级应用之独立关联与外键关联
- 浏览器主页被hao123贱贱的篡改的一种方式
- Open Cascade DataExchange DXF
- Android学习笔记之短信验证码的获取和读取
- List<T>保存为XML文件
- Android编译选项eng、user、userdebug的区别
- viewDidLoad && loadView
- Java 使用对话框选择文件并输出到控制台
- iOS-GCD多线程
- uva-442 Matrix Chain Multiplication
- python入门（Python和Pycharm安装）
- Chapter 2 User Authentication, Authorization, and Security（3）：保护服务器避免暴力攻击
- Spring Webflux: Kotlin DSL [片断]
- JavaSSM框架报HTTP Status 500 - Servlet.init() for servlet springMvc threw exception错误
- Emacs中的拼写检查
- one list to muti list
- 解题报告 『[USACO08NOV]Mixed Up Cows（状压动规）』
- HTTP消息头（HTTP headers）－常用的HTTP请求头与响应头
- [Android] 基于 Linux 命令行构建 Android 应用（六）：Android 应用签名
- XML与 实体的相互转化