两个有序链表的合并2.5

合并两个有序链表是一种常见的数据结构操作，特别是在需要对链表进行排序的时候。在给定的场景下，假设我们有两个已经排好序的单向链表，任务是将它们合并成一个新的有序链表。

首先，我们可以创建一个新的空链表作为结果，并初始化它的头节点为None。然后，我们需要设置两个指针，分别指向两个输入链表的头部。接着进入一个循环：

1. 比较当前两个指针所指向的节点值，选择较小的一个节点将其添加到结果链表，并将对应链表的指针向前移动一步。
2. 如果其中一个链表遍历完了，我们将另一个链表剩余的部分直接添加到结果链表上。

这个过程会一直持续到两个输入链表都遍历完毕。最后的结果链表就是合并后的有序链表。

以下是伪代码形式的合并过程：

def merge_sorted_lists(list1, list2):
    result = None
    if list1 is not None and list2 is not None:
        if list1.val < list2.val:
            result = list1
            result.next = merge_sorted_lists(list1.next, list2)
        else:
            result = list2
            result.next = merge_sorted_lists(list1, list2.next)
    return result or (list1 if list1 is not None else list2)