合并K个排序链表

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

def mergeKLists(self, lists):
        all_list=[]
        for each in lists:
            while each:
                all_list.append(each.val)
                each=each.next
        all_list.sort()
        head=ListNode(0)
        p=head
        for i in all_list:
            p.next=ListNode(i)
            p=p.next
        p.next=None
        p=head.next
        del head
        return p

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        interval = 1
        lists_len = len(lists)
        while interval<lists_len:
            for i in range(0,lists_len-interval,interval * 2):
                lists[i] = self.merge(lists[i], lists[i + interval]);
            interval *= 2
        return lists[0] if len(lists) > 0 else None
    def merge(self,l1, l2):
        if l1 is None:
            return l2
        if l2 is 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