21. 合并两个有序链表(Easy)

题目描述

Leetcode 地址

样例

Input：1->2->4, 1->3->4
Output：1->1->2->3->4->4

解题思路

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

伪节点

• 创建新的伪节点作为合并的头，按照大小加入节点后。
• 最后有剩余的节点，一口气加入。

递归

• 使用较小的链表的 头结点 作为 头
• 因为如果有一列是空的，那么应该范围另外一列。对 终止条件 的设置很巧妙

Python示例

伪节点【推荐】

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummpyHead = ListNode(None)
        p = dummpyHead
        while l1 and l2:
            if l1.val < l2.val:
                p.next = l1
                l1 = l1.next
            else:
                p.next = l2 
                l2 = l2.next 
            p = p.next 
        p.next = l1 if l1 else l2
        return dummpyHead.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