内容简介:拼命刷题 (๑• . •๑)题目:合并
这是崔斯特的第八十四篇原创文章
拼命刷题 (๑• . •๑)
题目:合并 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个排序链表》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- Java中的合并排序算法
- LeetCode (25):合并两个排序的链表
- php数组的21个操作合并,拆分,删除,排序…
- LeetCode算法系列.0023_合并K个排序链表
- 剑指Offer对答如流系列 - 合并两个排序的链表
- 分组字符合并SQL语句 按某字段合并字符串之一(简单合并)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。