Merge K Sorted Linked Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
URL: https://leetcode.com/problems/merge-k-sorted-lists/
import heapq
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if lists == [] or lists == None:
return None
else:
pq = []
for i in range(len(lists)):
if lists[i] != None:
item = (lists[i].val, i, lists[i])
heapq.heappush(pq, item)
dummy = ListNode(0)
p = dummy
while pq != []:
heap_item = heapq.heappop(pq)
p.next = heap_item[2]
p = p.next
if heap_item[2].next != None:
item = (heap_item[2].next.val, heap_item[1], heap_item[2].next)
heapq.heappush(pq, item)
return dummy.next