题目描述

解题思路

相信大家都做过两个有序链表合并的习题吧。该题的解决思路是建立在两个有序链表合并的基础上。使用的方法是递归。

两个有序链表合并思路

1.如果其中一个链表为空，直接返回另一个链表，因为一个空链表和非空链表的合并结果就是非空链表本身。
2.比较两个链表头节点的值，将值较小的节点作为合并后链表的当前节点，然后递归地对剩余部分进行合并。
3.递归地比较两个链表的下一个节点，直到其中一个链表为空，然后返回另一个链表的剩余部分
可能描述起来没那么通俗易懂，大家可以根据代码，自己定义两个链表，走一遍这个过程，就会理解了。

两个有序链表合并代码

        def Merge(list1,list2):
            if list1==None:
                return list2
            if list2==None:
                return list1
            if list1.val<list2.val:
                list1.next=Merge(list1.next,list2)
                return list1
            else:
                list2.next=Merge(list1,list2.next)
                return list2

在这一步完成，之后，我们只需要从头开始遍历所有链表，然后每两个合并。这就要求多个链表的数目大于2，否则就要进行特别的处理，主要是链表为空的情况判断。

最后的代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        def Merge(list1,list2):
            if list1==None:
                return list2
            if list2==None:
                return list1
            if list1.val<list2.val:
                list1.next=Merge(list1.next,list2)
                return list1
            else:
                list2.next=Merge(list1,list2.next)
                return list2
        if len(lists)==0:
            return None
        if len(lists)==1:
            return lists[0]
        else:
            result=Merge(lists[0],lists[1])
            for i in range(2,len(lists)):
                result=Merge(result,lists[i])
            return result