• 每日一题python85:合并两个有序链表


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

    示例 1:

    输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4]
    示例 2:

    输入:l1 = [], l2 = [] 输出:[]
    示例 3:

    输入:l1 = [], l2 = [0] 输出:[0]

    提示:

    两个链表的节点数目范围是 [0, 50]
    -100 <= Node.val <= 100 l1 和 l2 均按 非递减顺序 排列

    程序说明:
    方法一:先构建一个哑节点,作为新链表的head,不停遍历并且比较list1和list2的节点值,然后按顺序存入新链表里。若后面出现其中一个list为空了,就直接将其后面的链表接入新链表后面即可。具体如图:(ps:链表题目画图解决会是一个较好的方法)
    在这里插入图片描述

    方法二:会发现方法一需要开辟一个新的链表,这样会使内存空间消耗增大,因此方法二用了递归的方法,直接在两list中进行数值比较并连接。
    全部代码:
    方法一:

    # Definition for singly-linked list.
    # 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]:
        	phead = ListNode(0)
            p = phead
            while list1 and list2:
                if list1.val <= list2.val:
                    p.next = list1
                    list1 = list1.next
                else:
                    p.next = list2
                    list2 = list2.next            
                p = p.next
             
            if list1 is not None:
                p.next = list1
            else:
                p.next = list2
            return phead.next
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    方法二:

    # Definition for singly-linked list.
    # 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]:
            if list1 is None:
                return list2
            elif list2 is None:
                return list1
            elif list1.val < list2.val:
                list1.next = self.mergeTwoLists(list1.next, list2)
                return list1
            else:
                list2.next = self.mergeTwoLists(list1, list2.next)
                return list2
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    题目来源:力扣(leetcode)

  • 相关阅读:
    MARKDOWN 文档图片编码嵌入方案
    vue3中使用vue-echarts
    我终于会写 Java 的定时任务了!
    IDEA的日常快捷键大全
    GitLab存储空间满了
    【LeetCode:2760. 最长奇偶子数组 | 模拟 & 双指针】
    快速安装k8s
    【学习日志】2022.09.18 Bikablo 指针 -> 雷火
    Python学习 day01(注意事项)
    FPGA---UDP通信求助
  • 原文地址:https://blog.csdn.net/qq_52669357/article/details/125517092