合并k个已排序的链表

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        # 堆队列算法，比如优先队列
        import heapq
        pre = ListNode(-1)
        cur = pre
        # 优先队列
        head = []
        # 遍历所有链表
        for i in range(len(lists)):
            if lists[i]:
                # 将链表头结点放入优先队列中，放入头结点，就相当于放入了整个链表！！
                heapq.heappush(head, (lists[i].val, i))
                # 各链表首指针往后移动
                lists[i] = lists[i].next
        # 合并队列中已有的节点
        while head:
            # 取得节点值域，及其在对应链表中节点的下标位置
            # 由于优先队列的性质:heappop()的就是当前队列中最小元素
            val, index = heapq.heappop(head)
            # 构造节点并入结果链表
            cur.next = ListNode(val)
            # 指针往后顺移
            cur = cur.next
            # 若最小节点对应的链表不为空
            if lists[index]:
                # 将对应链表的下一个节点入队
                heapq.heappush(head, (lists[index].val, index))
                # 遍历该链表的指针往后顺移
                lists[index] = lists[index].next
        return pre.next

class Solution:
    def mergeKLists(self , lists ):
        # write code here
        if not lists:
            return None
        if len(lists) <= 1:
            return lists[0]
        if len(lists) == 2:
            return self.mergeTwoLists(lists[0], lists[1])
        
        idx = len(lists) // 2
        left = self.mergeKLists(lists[:idx])
        right = self.mergeKLists(lists[idx:])
        return self.mergeKLists([left, right])
    
    def mergeTwoLists(self , p1, p2):
        # write code here
        head = ListNode(0)
        curr = head
        while p1 and p2:
            if p1.val <= p2.val:
                curr.next = p1
                p1 = p1.next
            else:
                curr.next = p2
                p2 = p2.next
                
            curr = curr.next
        if p2:
            curr.next = p2
        if p1:
            curr.next = p1

        return head.next

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param lists ListNode类一维数组 
# @return ListNode类
#
class ListNode:
    def __init__(self,x):
        self.val=x
        self.next=None
class Solution:
    def mergetwolist(self,l1,l2):
        #对k条链表进行合并，可以思考采用的方法是两两合并的方法
        head=ListNode(0)
        p=head
        while l1 and l2:
            if l1.val<l2.val:
                p.next=l1
                l1=l1.next
            else:
                p.next=l2
                l2=l2.next
            p=p.next
        if l1:
            p.next=l1
        elif l2:
            p.next=l2
        return head.next
    def mergeKLists(self , lists ):
        # write code here
        if not lists:
            return None
        k=len(lists)
        if k==1:
            return lists[0]
        if k==2:
            return self.mergetwolist(lists[0],lists[1])
        s1=self.mergeKLists(lists[:(k//2)])
        s2=self.mergeKLists(lists[(k//2):])
        return self.mergetwolist(s1,s2)