Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists):
sMap = {}
eMap = {}
h = ListNode(None)
for l in lists:
while l is not None:
if l.val not in sMap:
sMap[l.val] = l
eMap[l.val] = l
else:
eMap[l.val].next = l
eMap[l.val] = l
l = l.next
keys = sMap.keys()
if len(keys) == 0:
return h.next
keys = sorted(keys)
p = h
for k in keys:
p.next = sMap[k]
p = eMap[k]
return h.next
sMap保存目前节点的值
eMap保存节点连接点
当遇到在sMap中出现过的值，就将更新eMap，即更新连接点，
当更新 eMap[l.val].next时，其实就是在更新sMap
