23. Merge k Sorted Lists

用字典记录下左右的val值，然后排序，然后创建结点

# 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
        """
        fep = {}
        nex = True
        while nex:
            nex = False
            for i, l in enumerate(lists):
                if l:
                    v = l.val
                    if v not in fep:
                        fep[v] = 1
                    else:
                        fep[v] += 1
                    lists[i] = l.next
                    if lists[i]:
                        nex = True
        head = ListNode(0)
        p = head
        for f in sorted(fep):
            for i in range(fep[f]):
                p.next = ListNode(f)
                p = p.next
        return head.next

另外一种办法是递归法：

# 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
        """
        return self.partion(lists, 0, len(lists)-1)
    def partion(self, lists, s, e):
        if s == e:
            return lists[s]
        if s < e:
            q = (s + e) / 2
            l1 = self.partion(lists, s, q)
            l2 = self.partion(lists, q+1, e)
            return self.merge(l1,l2)
        else:
            return None
    def merge(self, l1, l2):
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        if l1.val <= l2.val:
            l1.next = self.merge(l1.next, l2)
            return l1
        else:
            l2.next = self.merge(l1, l2.next)
            return l2