描述

合并 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)

我们可以用现有的节点进行所有操作,不需要新增节点