[数据结构与算法]21. 合并两个有序链表 23. 合并K个升序链表【每日一题】

21. 合并两个有序链表

思路

? ? ? ? ? 思路比较简单常规思路，和合并有序数组一样，分别去一个出来，然后比大小，结果加入小的一个，小的对应链表一个取新的出来，继续比较，直到其中一个比完了

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1==None:
            return list2
        if list2==None:
            return list1

        # 循环
        res = ListNode(None)
        node = res
        while list1!=None and list2!=None:
            if list1.val<list2.val:
                node.next = list1
                list1 = list1.next
            else:
                node.next = list2
                list2=list2.next
            node = node.next
        if list1!= None:
            node.next = list1
        else:
            node.next = list2
        
        return res.next

为了更好的过渡到合并K个的，我们介绍一下递归形式的；你想想，我们有一个函数可以合并两个链表，那么我只需要比较最开始两个链表的头大小似乎就行了

• 如果第一个链表头小，那么我直接调用函数合并第一个链表后面的和第二个链表得到一个有序列表，且这个有序列表的最小值肯定比第一个链表头大（这不是废话吗，原来的链表都是有序的，那这样比较得到的头肯定是最小的）
• 如果第二个链表头小，那么我直接调用函数合并第二个链表后面的和第一个链表得到一个有序列表

在这儿，我们假设这个函数能做到这个合并两个有序链表，那么你会发现比较完第一个后，又变成，两个有序链表的合并，随意递归是有搞头的，注意写好递归终止条件

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1==None:
            return list2
        if list2==None:
            return list1
        
       # 递归
        if list1.val<list2.val:
            list1.next = self.mergeTwoLists(list1.next,list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1,list2.next)
            return list2

23. 合并K个升序链表

? ? ? ? ? 思路也还好，就是刚才递归的想法，我们假设已经有一个函数可以实现合并K个升序链表，是吧，那么我现在把k个链表从中间分成两部分，然后分别调用这个函数，是不是就把前面的一半合并好了，后面的一半也合并好了，最后调用合并两个有序的代码把前后两部分合并。递归出口是那些那

1. 待合并的是空，返回空
2. 待合并的是1个，返回他自己
3. 待合并的是两个，调合并两个的，返回
4. 待合并的多个，那就分前后部分，然后前后都都调用这个合并k个的函数，最后调用合并两个的代码把前后两部分合并。

# 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]:
        n = len(lists)
        if n==0:
            return None
        elif n== 1:
            return lists[0]
        elif n==2:
            return  self.mergeTwoLists(lists[0],lists[1])
        
        mid = n//2
        l_list = []
        for i in range(mid):
            l_list.append(lists[i])

        r_list=[]
        for i in range(mid,n):
            r_list.append(lists[i])
            
        return self.mergeTwoLists(self.mergeKLists(l_list),self.mergeKLists(r_list))

    # 先把合并两个的抄过来
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1==None:
            return list2
        if list2==None:
            return list1
        
        if list1.val<list2.val:
            list1.next = self.mergeTwoLists(list1.next,list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1,list2.next)
            return list2