题目：

思路：

1. 初始化伪头节点pre,节点curr指向pre
2. 循环比较：
   1. 当list1.val <= list2.val:curr的后继节点是list1，并且list1向后走一步
   2. 当list1.val > list2.val:curr的后继节点是list2，并且list2向后走一步
   3. curr向后走一步，curr = curr.next
3. 合并尾部：
   1. 若list1不为空，那么list1加到curr后
   2. 反之，list2加到curr后
4. 返回：合并后的链表在伪头节点pre后，所以返回pre.next

代码：

# 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]:
        pre = ListNode(-1) # 伪头节点
        curr = pre
        while list1 and list2:
            if list1.val <= list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            curr = curr.next #这步不能忘记
        #合并尾部
        curr.next = list1 if list1 else list2
        return pre.next