21. 合并两个有序链表

• 题目
• 代码

题目

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

示例 1：

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

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

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

代码

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 创建一个新的头节点
        new_head = ListNode(0)
        tail = new_head#尾指针

        # 依次比较两个链表的节点，并将较小的节点插入到新链表的尾部
        while list1 !=None and list2!=None:
            if list1.val <= list2.val:
                tail.next = list1#放在新的链表后面
                list1 = list1.next#往后移继续判断
            else:
                tail.next = list2#放在新的链表后面
                list2 = list2.next#往后移继续判断
            tail = tail.next
        # 将剩余的节点直接连接到新链表的尾部
        if list1:#如果list1还没遍历完
            tail.next = list1#直接加在后面
        elif list2:#如果list2还没遍历完
            tail.next = list2#直接加在后面

        return new_head.next