leetcode 23. Merge k Sorted Lists

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