算法总结|合并K个排序链表
发布于 5 年前 作者 halu886 3207 次浏览 来自 分享

该文章阅读需要5分钟,更多文章请点击本人博客halu886

描述

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

解题思路

暴力法

最直接的方法则是暴力法

  1. 遍历所有的链表，将链表放入一个数组中
  2. 将数组排序
  3. 再将数组生成链表

这个方法可以将链表转换数组，通过我们熟悉且易于操作的结构进行排序，再转换成有序的排序链表

假设N是链表的总长度，则

  • 时间复杂度为O(N log N)
  1. 将链表转化成数组，时间复杂度为O(N)
  2. 对数组进行排序（设这里为快速排序），时间复杂度为O(N log N)。推导过程
  3. 将数组转换成链表，时间复杂度为O(N)
  • 空间复杂度为O(N)
  1. 排序的空间复杂度为O(logN)
  2. 新建一个有序列表O(N)

逐一比较

  1. 将每一个列表的进行比较。
  2. 取最小的节点放置再链表最后。
  • 时间复杂度 O(kN)，k为链表的数量
  1. 每个节点都需要比较(k-1)次
  2. 总共有N个节点
  • 空间复杂度 O(1)
  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为列表的数量
  1. 弹出操作时，优先队列排序为 O(log k),找到最小节点的时间开销仅仅为 O(1)
  2. N个节点进行排序
  • 空间复杂度为 O(log k)
  1. 对节点的排序不需要新建节点，则为O(1)
  2. 优先队列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为节点总数量
  1. 合并两个列表的时间耗时为O(m+n),m和n分别为两个列表的节点数
  2. k-1次合并，对耗时累加为O(kN)
  • 空间复杂度 O(1)
  1. 旧节点能够复用，不需要新建节点

分治

对上面的方法进行优化，所有列表一一进行配对合并。 每次配对需要遍历所有N个节点，共需要配对log2N。

1

  • 时间复杂度O(N log k),N为节点总数量，k为列表数量
  1. 进行合并的时间耗时为O(N),N为所有节点总和
  2. 总共需要log2k次排序
  • 空间复杂度为O(1)
  1. 我们可以用现有的节点进行所有操作，不需要新增节点
回到顶部