pta两个有序链表的合并

当有两个已排序的链表（即每个节点的值都小于其后继节点的值），需要将它们合并成一个新的有序链表时，可以采用归并排序的思想。以下是基本的算法步骤：

1. **创建新链表**：首先，创建一个新的空链表，这个链表将是最终合并结果。

2. **遍历比较**：分别从两个输入链表的头部开始，比较当前节点的值。选择较小的那个节点，将其添加到新链表，并移动指向该节点的指针到下一个节点。如果其中一个链表到达了终点，就直接将另一个链表剩余的部分接到新链表的末尾。

3. **继续迭代**：重复上述过程，直到两个链表都被遍历完。

以下是伪代码表示：

def merge_sorted_lists(list1, list2):
    dummy = ListNode(0)  # 创建虚拟头节点
    current = dummy  # 初始化合并后的链表头

    while list1 and list2:
        if list1.val < list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next

    # 如果有一个链表未遍历完，将其余部分连接到新链表的末尾
    if list1:
        current.next = list1
    elif list2:
        current.next = list2

    return dummy.next