算法总结|合并K个排序链表
该文章阅读需要5分钟,更多文章请点击本人博客halu886
描述
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
解题思路
暴力法
最直接的方法则是暴力法
- 遍历所有的链表,将链表放入一个数组中
- 将数组排序
- 再将数组生成链表
这个方法可以将链表转换数组,通过我们熟悉且易于操作的结构进行排序,再转换成有序的排序链表
假设N是链表的总长度,则
- 时间复杂度为O(N log N)
- 将链表转化成数组,时间复杂度为O(N)
- 对数组进行排序(设这里为快速排序),时间复杂度为O(N log N)。推导过程
- 将数组转换成链表,时间复杂度为O(N)
- 空间复杂度为O(N)
- 排序的空间复杂度为O(logN)
- 新建一个有序列表O(N)
逐一比较
- 将每一个列表的进行比较。
- 取最小的节点放置再链表最后。
- 时间复杂度 O(kN),k为链表的数量
- 每个节点都需要比较(k-1)次
- 总共有N个节点
- 空间复杂度 O(1)
- 将每一个存在的节点放在最后,不用声明新的节点
击败了8.98%,耗时608ms
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
ListNode *mergeKLists(vector<ListNode *> &lists)
{
if (lists.size() == 0)
{
return {};
}
ListNode *p_index;
ListNode *p_head;
p_index = p_head = NULL;
int first_index = 0;
for (; !isOver(lists);)
{
ListNode *p_temp = lists[0];
int num_p = 0;
for (int j = 0; j < lists.size(); j++)
{
if (!lists[j])
{
continue;
}
if (p_temp && lists[j]->val < p_temp->val)
{
p_temp = lists[j];
num_p = j;
}
else if (!p_temp)
{
p_temp = lists[j];
num_p = j;
}
}
if (p_head)
{
p_index->next = p_temp;
p_index = p_temp;
}
else
{
p_index = p_head = p_temp;
}
lists[num_p] = lists[num_p]->next;
}
return p_head;
}
bool isOver(vector<ListNode *> &lists)
{
for (int i = 0; i < lists.size(); i++)
{
if (lists[i])
{
return false;
}
}
return true;
}
};
用队列方法优化方法2
思路同上,但是通过优先队列进行每个列表的比较
- 时间复杂度 O(N log k),k为列表的数量
- 弹出操作时,优先队列排序为 O(log k),找到最小节点的时间开销仅仅为 O(1)
- N个节点进行排序
- 空间复杂度为 O(log k)
- 对节点的排序不需要新建节点,则为O(1)
- 优先队列O(k)的空间
击败98.87%,耗时32ms
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
struct cmp
{
bool operator()(ListNode *a, ListNode *b)
{
return a->val > b->val;
}
};
class Solution
{
public:
ListNode *
mergeKLists(vector<ListNode *> &lists)
{
if (lists.size() == 0)
{
return {};
}
ListNode *p_index;
ListNode *p_head;
p_index = p_head = NULL;
int first_index = 0;
priority_queue<ListNode *, vector<ListNode *>, cmp> pq;
for (int i = 0; i < lists.size(); i++)
{
if (lists[i])
{
pq.push(lists[i]);
}
}
while (!pq.empty())
{
ListNode *p_temp = pq.top();
pq.pop();
if (p_head)
{
p_index->next = p_temp;
p_index = p_temp;
}
else
{
p_index = p_head = p_temp;
}
if (p_temp->next)
{
pq.push(p_temp->next);
}
}
if (!p_head)
{
return {};
}
return p_head;
}
};
两两合并
分别将列表两两合并共k-1次
- 时间复杂度 O(kN),k为列表数量,N为节点总数量
- 合并两个列表的时间耗时为O(m+n),m和n分别为两个列表的节点数
- k-1次合并,对耗时累加为O(kN)
- 空间复杂度 O(1)
- 旧节点能够复用,不需要新建节点
分治
对上面的方法进行优化,所有列表一一进行配对合并。 每次配对需要遍历所有N个节点,共需要配对log2N。
- 时间复杂度O(N log k),N为节点总数量,k为列表数量
- 进行合并的时间耗时为O(N),N为所有节点总和
- 总共需要log2k次排序
- 空间复杂度为O(1)
- 我们可以用现有的节点进行所有操作,不需要新增节点