[Lintcode]128. Longest Consecutive Sequence/[Leetcode]23. Merge k Sorted Lists

本文主要是介绍[Lintcode]128. Longest Consecutive Sequence/[Leetcode]23. Merge k Sorted Lists，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

128. Longest Consecutive Sequence / 23. Merge k Sorted Lists

• 本题难度: Hard/Medium
• Topic: Data Structure - heap(别人的代码1用的是heap)

Description

Merge k sorted linked lists and return it as one sorted list.

Analyze and describe its complexity.

Example
Example 1:
Input: [2->4->null,null,-1->null]
Output: -1->2->4->null

Example 2:
Input: [2->6->null,5->null,7->null]
Output: 2->5->6->7->null

我的代码

"""
Definition of ListNode
class ListNode(object):def __init__(self, val, next=None):self.val = valself.next = next
"""class Solution:"""@param l1: ListNode l1 is the head of the linked list@param l2: ListNode l2 is the head of the linked list@return: ListNode head of linked list"""def mergeKLists(self, lists):# write your code herel = len(lists)if l == 0:return Noneleft = 0right = l-1return self.merge(left,right,lists)def merge(self,left,right,lists):if left == right:return lists[left]if left == right-1:return self.mergeTwoLists(lists[left],lists[right])mid = left+(right-left)//2return self.mergeTwoLists(self.merge(left,mid,lists),self.merge(mid+1,right,lists))def mergeTwoLists(self, l1, l2):# write your code hereif l1 is None:return l2if l2 is None:return l1res = pos = ListNode(0)while (l1 and l2):if l1.val < l2.val:pos.next = l1l1 = l1.nextelse:pos.next = l2l2 = l2.nextpos = pos.nextif l1:pos.next = l1else:pos.next = l2return res.next

别人的代码

1.heap

Lintcode Discussion评论区

"""
Definition of ListNode
class ListNode(object):def __init__(self, val, next=None):self.val = valself.next = next
"""
import heapq
class Solution:"""@param l1: ListNode l1 is the head of the linked list@param l2: ListNode l2 is the head of the linked list@return: ListNode head of linked list"""def mergeKLists(self, lists):if not lists:return Nonedummy = ListNode(-1)curr = dummyheap = []for ll in lists:while ll:heapq.heappush(heap, ll.val)ll = ll.nextwhile heap:# smallestnode = ListNode(heapq.heappop(heap))curr.next = nodecurr = curr.nextreturn dummy.next

2. Priority Queue 但是python3跑不通。因为compare的operation不能重定义。

10-line python solution with priority queue

from Queue import PriorityQueue
class Solution(object):def mergeKLists(self, lists):dummy = ListNode(None)curr = dummy q = PriorityQueue() #构建一个优先队列，里面元素是val和node，默认根据第一个元素排序了#将头结点放到优先队列中for node in lists:if node: q.put((node.val,node)) #将每个结点的下一个结点放入优先队列中。之后再取出最小的。#当下一个最小的是原来它后面的元素时，下一次取出来的就是这个元素，否则，各个链表所有比它大的最小元素也都在优先队列中了。while q.qsize()>0: curr.next = q.get()[1] #curr表示当前位置，初始值是无意义的头结点curr=curr.nextif curr.next: q.put((curr.next.val, curr.next)) #  如果取出来的点之后的点不为空，则放入优先队列中。return dummy.next

---

使用了优先队列。我之前没有用过。
读python 堆和优先队列的使用
常见函数

#向队列中添加元素
Queue.put(item[, block[, timeout]])
#从队列中获取元素
Queue.get([block[, timeout]])
#队列判空
Queue.empty()
#队列大小
Queue.qsize()

思路
merge
二分法
将两个有序数列merge可参照[165. Merge Two Sorted Lists/21. Merge Two Sorted Lists(https://www.cnblogs.com/siriusli/p/10364804.html)

• 时间复杂度 O(nlog(n))

这篇关于[Lintcode]128. Longest Consecutive Sequence/[Leetcode]23. Merge k Sorted Lists的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---