设计两个有序单链表的合并排序算法

设计一个有序单链表的合并排序算法通常涉及以下几个步骤：

1. **递归分解**：
- 将较长的列表分为两半，直到每个子列表只有一个元素。
- 这是递归的基础情况。

2. **合并过程**：
- 当有两个非空的子链表需要合并时：
- 创建一个新的头节点，将其初始化为空。
- 比较当前子链表的头节点和另一个子链表的头节点，将较小的那个节点添加到新链表，并移动相应的指针向前。
- 重复这个过程，直到其中一个子链表遍历完。
- 然后将剩余未遍历的链表的剩余部分添加到新链表的末尾。

3. **回溯**：
- 一旦所有的子链表都合并完毕，返回新的链表作为合并后的结果。

以下是合并排序算法的一个伪代码版本：

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