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

题目描述

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

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