算法题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

输入：l1 = [1,2,4], l2 = [1,3,4]

输出：[1,1,2,3,4,4]

提示要求

两个链表的节点数目范围是 [0, 50]

-100 <= Node.val <= 100

l1 和 l2 均按非递减顺序排列

算法提示： 递归，链表

代码如下

• 创建哑结点的链表方式进行排序

from typing import Optional
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        new_node = ListNode()  # 创建哑结点
        move_node = new_node  # move_node游标，用来移动
        while list1 and list2:
            if list1.val <= list2.val:  # 比较大小
                move_node.next = list1  # 较小值入新的链表
                list1 = list1.next  # 节点重新指向
            else:
                move_node.next = list2
                list2 = list2.next
            move_node = move_node.next  # 移动结果链表的尾指针
        move_node.next = list1 if list1 else list2  # 拼接未遍历完的节点
        return new_node.next  # 返回哑结点的后续链表

• 递归方式进行排序

class Solution:
    def mergeTwoLists01(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 终止条件，直到两个链表都空
        if not list1: return list2
        if not list2: return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists01(list1.next, list2)  # 进行递归
            return list1
        else:
            list2.next = self.mergeTwoLists01(list1, list2.next)
            return list2

• LeetCode大神版方法

class Solution:
    def mergeTwoLists02(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 大神缩写，采用递归方式；节点交换，使list1的节点值一直是小的，然后进行遍历，不太容易理解。
        if list1 and list2:
            if list1.val > list2.val:
                list1, list2 = list2, list1
            list1.next = self.mergeTwoLists(list1.next, list2)
        return list1 or list2

总结

1. 链表排序，创建一个哑结点，然后通过游标进行移动排序，最容易理解，而且不易出错！
2. 采用递归方法排序，比较简单，不过需要理解递归的特点！
3. 可以采用堆方法进行排序，把所有链表值都push到堆中，然后依次pop！
4. 人生苦短，我用python！

#python##学习##学习打卡#