美文网首页
【简单】Leetcode-21 合并两个有序链表

【简单】Leetcode-21 合并两个有序链表

作者: 砥砺前行的人 | 来源:发表于2021-05-10 15:12 被阅读0次

    题目描述

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

    image.png
    输入:l1 = [1,2,4], l2 = [1,3,4]
    输出:[1,1,2,3,4,4]
    

    解法一

    挨个比较,最后将多出来的追加末尾

    class Solution:
        def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
            cur = res = ListNode() # 虚拟头结点
            # 挨个比较
            while l1 and l2:
                if l1.val > l2.val:
                    cur.next = l2
                    l2 = l2.next
                else:
                    cur.next = l1
                    l1 = l1.next
                cur = cur.next
            
            # 将两个链表中未比较的部分追加到末尾
            cur.next = l1 if l1 else l2    
            return res.next
    

    解法二

    递归。基本思路与解法一相同,只是使用递归完成迭代

    class Solution:
        def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
            if not l1: return l2
            if not l2: return l1
            if l1.val <= l2.val:
                l1.next = self.mergeTwoLists(l1.next,l2)
                return l1
            else:
                l2.next = self.mergeTwoLists(l1,l2.next)
                return l2
    

    相关文章

      网友评论

          本文标题:【简单】Leetcode-21 合并两个有序链表

          本文链接:https://www.haomeiwen.com/subject/kcdidltx.html