在Python中合并k个排序列表

假设我们有一些列表，这些列表已排序。我们必须将这些列表合并为一个列表。为了解决这个问题，我们将使用堆数据结构。因此，如果列表为[1,4,5]，[1,3,4]，[2,6]，则最终列表将为[1,1,2,3,4,4,5,6]。

为了解决这个问题，我们将遵循以下步骤-

堆一堆

对于列表中的每个链接列表l-

如果不为0，则将I插入堆

res：=null和res_next：=null

做一个无限循环-

下一个res_next：=temp，temp：=下一个temp，res_next：=下一个res_next

如果temp不为null，则将temp插入堆中

下一个res_next：=null

res：=temp，res_next：=temp

temp：=temp的下一个元素

如果temp不为零，则将temp插入堆中

下一个res：=null

temp：=最小堆

如果堆没有元素，则返回res

如果res为0，则

否则-

示例

让我们看下面的实现以更好地理解-

class ListNode: def __init__(self, data, next = None): self.val = data self.next = next def make_list(elements): head = ListNode(elements[0]) for element in elements[1:]: ptr = head while ptr.next: ptr = ptr.next ptr.next = ListNode(element) return head def print_list(head): ptr = head print([, end = "") while ptr: print(ptr.val, end = ", ") ptr = ptr.next print(]) class Heap: def __init__(self): self.arr = [] def print_heap(self): res = " " for i in self.arr: res += str(i.val) + " " print(res) def getVal(self,i): return self.arr[i].val def parent(self,i): return (i-1)//2 def left(self,i): return (2*i + 1) def right(self,i): return (2*i + 2) def insert(self,value): self.arr.append(value) n = len(self.arr)-1 i = n while i != 0 and self.arr[i].val<self.arr[self.parent(i)].val: self.arr[i],self.arr[self.parent(i)] = self.arr[self.parent(i)],self.arr[i] i = self.parent(i) def heapify(self,i): left = self.left(i) right = self.right(i) smallest = i n= len(self.arr) if left<n and self.getVal(left)<self.getVal(smallest): smallest = left if right <n and self.getVal(right)<self.getVal(smallest): smallest = right if smallest!=i: self.arr[i],self.arr[smallest] = self.arr[smallest],self.arr[i] self.heapify(smallest) def extractMin(self): n = len(self.arr) if n==0: return # if n== 1: temp =self.arr[0] self.arr.pop() return temp root = self.arr[0] self.arr[0] = self.arr[-1] self.arr.pop() self.heapify(0) return root class Solution(object): def mergeKLists(self, lists): heap = Heap() for i in lists: if i: heap.insert(i) res = None res_next = None while True: temp = heap.extractMin() if temp == "#": return res if not res: res = temp res_next = temp temp = temp.next if temp: heap.insert(temp) res.next = None else: res_next.next = temp temp = temp.next res_next=res_next.next if temp: heap.insert(temp) res_next.next = None ob = Solution() lists = [[1,4,5],[1,3,4],[2,6]] lls = [] for ll in lists: l = make_list(ll) lls.append(l) print_list(ob.mergeKLists(lls))

输入项

[[1,4,5],[1,3,4],[2,6]]

输出结果

[1, 1, 2, 3, 4, 4, 5, 6, ]