刷题之合并K个排序链表

栏目: 数据库 · 发布时间: 5年前

内容简介:拼命刷题 (๑• . •๑)题目:合并
这是崔斯特的第八十四篇原创文章

拼命刷题 (๑• . •๑)

刷题之合并K个 <a href='https://www.codercto.com/topics/21904.html'>排序</a> 链表

题目:合并 k 个排序链表,返回合并后的排序链表。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

思路一

21. 合并两个有序链表 的基础上,我们已经能够解决两个有序链表的问题,现在是k个有序链表,我们可以将第一二个有序链表进行合并,然后将新的有序链表再继续跟第三个有序链表合并,直到将所有的有序链表合并完成。 这样做思路上是可行的,但是算法的时间复杂度将会很大,具体就不计算了。有兴趣的自己计算下。

思路二

根据思路一,我们是一个一个地将有序链表组成新的链表,这里一个进行了k-1次两个有序链表的合并操作。而且随着新链表越来越大,时间复杂度也会越来越高。 这里有一种简化的方式,可以先将k个有序链表先以2个链表为一组进行合并,得出结果后,再将所有的新有序链表继续上面的方式,2个链表为一组进行合并。直至将所有的有序链表进行合并。 这个思路会比思路一的算法复杂度少一点。

思路三(推荐)

我们换个不一样的思路。我们先遍历一次所有的链表中的元素。然后将元素全部放在一个数组里面。接着对这个数组进行排序,最终将排序后的数组里面的所有元素链接起来。 这种方案的复杂度和代码量会比前集中思路更好,更简单。

空间复杂度:因为需要一个数组,所以需要额外的空间。这个空间的大小就是链表元素的个数 时间复杂度:假设一个是n个元素,对链表进行遍历(n),对数组进行排序(排序算法可以达到nlogn),最终链接所有元素(n),就是 (n+nlogn+n),也就是O(nlogn)。

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        nodeList = []
        for i in range(len(lists)):
            currentNode = lists[i]
            while currentNode:
                nodeList.append(currentNode)
                currentNode = currentNode.next

        nodeList = sorted(nodeList, key=lambda x: x.val)

        tempHead = ListNode(0)
        currentNode = tempHead
        for i in range(len(nodeList)):
            currentNode.next = nodeList[i]
            currentNode = currentNode.next

        return tempHead.next

思路四

偷懒方法,使用内置库 heapq ,最小堆, 每个list有一个指针, k个指针放入堆中, 每次pop出最小的, 然后指向相应list的下一个node, 再push入堆。

最小堆是一个数组, 所有元素满 heap[k] <= heap[2*k+1]heap[k] <= heap[2*k+2] , heap[0]即堆顶最小。

# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
 
class Solution:
    # @param a list of ListNode
    # @return a ListNode
    def mergeKLists(self, lists):
        heap = []
        for node in lists:
            if node != None: 
                heap.append((node.val, node))
        heapq.heapify(heap)
        head = ListNode(0)
        curr = head
        while heap:
            pop = heapq.heappop(heap)
            curr.next = ListNode(pop[0])
            curr = curr.next
            if pop[1].next: 
                heapq.heappush(heap, (pop[1].next.val, pop[1].next))
        return head.next

以上所述就是小编给大家介绍的《刷题之合并K个排序链表》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

图说区块链

图说区块链

徐明星、田颖、李霁月 / 中信出版社 / 2017-7-1 / 59.00元

区块链,如瑞士仪表般精密,如互联网般惊世骇俗,它在以神一般的节奏颠覆社会。 当新兴技术来临时,你可以选择规避——如果明天也可以规避的话。区块链也一样。 作为一个现象级概念,金融科技创新在过去几年迎来了奇点式发展。其中最引人注目的当属区块链技术。区块链技术正在动摇全球金融基础设施,它是全球顶级银行和其他金融机构重点追逐的领域。毫无疑问,区块链是未来5年最有前景的行业之一。 《图说区......一起来看看 《图说区块链》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

随机密码生成器
随机密码生成器

多种字符组合密码