题解 | #牛群的合并#

• 题目考察的知识点 : 链表操作,分治算法 ,合并有序链表
• 题目解答方法的文字分析：

1. 利用分治思想,两两合并链表,合并后还是有序的。
2. 重复合并过程,直到全部链表合并为一个有序链表。
3. 合并两个链表采用类似归并排序的思路,比较两个链表的头元素,依次连接较小的元素。

• 本题解析所用的编程语言：Python
• 完整且正确的编程代码

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param lists ListNode类一维数组 
# @return ListNode类
#
class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        def mergeList(l1, l2):
            dummy = ListNode(-1)
            tail = dummy
            while l1 and l2:
                if l1.val < l2.val:
                    tail.next = l1
                    l1 = l1.next
                else:
                    tail.next = l2
                    l2 = l2.next
                tail = tail.next
            if l1:
                tail.next = l1
            if l2:
                tail.next = l2
            return dummy.next

        if len(lists) == 0:
            return None
        while len(lists) > 1:
            mergedLists = []
        
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if (i + 1) < len(lists) else None
                mergedList = mergeList(l1, l2)
                mergedLists.append(mergedList)
            lists = mergedLists
        return lists[0]