```
# 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 not lists:
return []
heap = []
firstlists = []
for i in range(len(lists)):
firstlists.append(lists[i])
for i in range(len(firstlists)):
if firstlists[i]:
val = firstlists[i].val
firstlists[i] = firstlists[i].next
heapq.heappush(heap, (val, i))
result = []
while heap:
val, index = heapq.heappop(heap)
result.append(val)
if firstlists[index]:
val = firstlists[index].val
firstlists[index] = firstlists[index].next
heapq.heappush(heap, (val, index))
return result
```