将两个有增序的单链表合并为一个增序的单链表

将两个已排序的单链表合并成一个新的有序单链表的过程通常称为归并操作。这里是一个基本的步骤：

1. **创建新节点**：首先，创建一个新的空链表，这个新链表将成为结果。

2. **遍历链表**：同时从两个输入链表的头部开始比较元素。选择较小的那个元素，并将其添加到新链表中，然后将选中的元素所指向的链表移动到下一个节点。

3. **递归或迭代**：继续上述过程，直到其中一个链表为空。此时，将另一个非空链表的所有剩余元素依次添加到新链表的末尾。

4. **连接剩余部分**：如果有一个链表还有剩余节点，需要将它们链接到新链表的末尾。

以下是伪代码示例：

def merge_sorted_lists(list1, list2):
    if not list1:  # 如果list1为空，直接返回list2
        return list2
    elif not list2:  # 如果list2为空，直接返回list1
        return list1
    
    if list1.val < list2.val:  # 比较当前头节点的值，选择较小的
        new_head = list1
        new_head.next = merge_sorted_lists(list1.next, list2)
    else:
        new_head = list2
        new_head.next = merge_sorted_lists(list1, list2.next)
    
    return new_head