1-4 两个有序链表序列的合并

将两个非降序链表合并成一个新的非降序链表的方法有多种。一种常见的方法是使用双指针来遍历两个链表，并逐个比较节点的值，将较小的节点添加到新的链表中。具体步骤如下：

1. 创建一个新的链表头节点s3，并创建一个指针p3指向s3。
2. 创建两个指针p1和p2分别指向链表s1和s2的头节点。
3. 比较p1和p2指向的节点的值，将较小的节点添加到新链表s3中，并将对应指针后移一位。
4. 重复步骤3，直到p1或p2为空。
5. 将p1或p2中剩余的节点添加到s3的末尾。
6. 返回新链表s3。

下面是一个Python的实现示例：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)  # 创建一个哑节点作为新链表的头节点
    p3 = dummy  # 新链表的指针p3
    p1, p2 = l1, l2  # 两个链表的指针p1和p2

    while p1 and p2:
        if p1.val <= p2.val:
            p3.next = p1
            p1 = p1.next
        else:
            p3.next = p2
            p2 = p2.next
        p3 = p3.next

    p3.next = p1 if p1 else p2

    return dummy.next

# 示例用法
l1 = ListNode(1)
l1.next = ListNode(3)
l1.next.next = ListNode(5)

l2 = ListNode(2)
l2.next = ListNode(4)
l2.next.next = ListNode(6)

l3 = mergeTwoLists(l1, l2)
while l3:
    print(l3.val, end=" ")
    l3 = l3.next

输出为：1 2 3 4 5 6