力扣题解:23.合并K个升序链表(困难)

前言

这道题是合并两个有序链表的升级版,理论层面的难度并不算大,在编码过程中可能涉及到一些深一些的知识点,本题采用了优先队列,并自定义了比较器实现小顶堆。

该题涉及:

  • 优先队列

题目

给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:

输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2:

输入:lists = []
输出:[]

示例 3:

输入:lists = [[]]
输出:[]

提示:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i]按升序排列
  • lists[i].length的总和不超过10^4

思路:我们思考对两个链表进行合并,有以下过程,我们总是采取两个链表中值较小的一个进行合并操作。

1->3->4    3->4       3->4      3->4       3->4          null
		->         ->        ->         ->            ->
1->1->2    1->1->2    1->2      2          null          null

null    -> 1       -> 1->1   -> 1->1->1 -> 1->1->1->2

-> 1->1->1->2->3->4

对于k个链表,我们当然可以两两合并,但是这样会重复遍历很多元素。能不能一次合并k个链表呢?
我们考虑对于两个链表的合并,我们总是拿值较小的一个进行合并,拓展至k个链表,那就是我们拿值最小的一个进行合并操作。
例如有3个链表的合并,我们总是拿三个链表头节点中值最小的一个进行合并操作。

1->3    3       3       3          null
     ->      ->      ->         ->            -> ...
2->3    2->3    2->3    3          3
     ->      ->      ->         ->            -> ...
1->4    1->4    4       4          4          

null -> 1    -> 1->1 -> 1->1->2 -> 1->1->2->3 -> ...

原理到这部分就结束了,到了编码问题,我们采用优先队列来实现。
priority_queue是优先队列,其队首元素总是最大或最小的,维护其有序性的时间复杂度为O(logn),采用堆的方式进行排序,这样我们每次都能很快的拿到最小的那个元素。

题解:

  • 时间复杂度:O(knlogk),其中k为链表数,n为某个链表的最大节点数。我们最多会遍历kn个节点,而每次遍历维护有序性的时间复杂度为O(logk)
class Solution {
public:
    struct compare{//自定义比较器
        bool operator()(ListNode* n1, ListNode* n2){
            return n1->val > n2->val;
        }
    };

    //采用自定义比较器,实现小顶堆,因为默认大顶堆
    priority_queue <ListNode*, vector<ListNode*>, compare> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node != nullptr) 
	            q.push(node);
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f;
            tail = tail->next;
            if (f->next != nullptr)
	            q.push(f->next);
        }
        return head.next;
    }
};
上一篇 下一篇

评论 | 0条评论