使用数据结构与算法已知两个非降序链表序列S1与S2,设计函数构造出S1与S2合并后的新的非降序链表S3。 输入格式: 输入分两行,分别在每行给出由若干个正整数构成的非降序序列,用−1表示序列的结尾(−1不属于这个序列

为了将两个非降序链表S1和S2合并成一个新的非降序链表S3，你可以采用双指针法。以下是步骤：

1. 创建一个新的空链表S3作为结果，并设置两个指针p1和p2分别为S1和S2的头节点。

2. 比较p1和p2所指向的元素：
- 如果p1的值小于或等于p2的值，将p1所指的节点添加到S3中，并移动p1到下一个节点；
- 否则，将p2所指的节点添加到S3中，并移动p2到下一个节点。

3. 分别处理两个链表的剩余部分：
- 当其中一个链表为空时，将另一个链表的所有剩余节点依次添加到S3中。

4. 最后返回S3的头节点，即为合并后的链表。

这里是一个伪代码示例：

function mergeSortedLists(S1Head, S2Head):
    result = None
    p1 = S1Head
    p2 = S2Head

    while p1 is not None and p2 is not None:
        if p1.value <= p2.value:
            if result is None:
                result = ListNode(p1.value)
            else:
                result.next = ListNode(p1.value)
            p1 = p1.next
        else:
            if result is None:
                result = ListNode(p2.value)
            else:
                result.next = ListNode(p2.value)
            p2 = p2.next

    # 将剩余未遍历完的链表添加到结果中
    while p1 is not None:
        if result is None:
            result = ListNode(p1.value)
        else:
            result.next = ListNode(p1.value)
        p1 = p1.next

    while p2 is not None:
        if result is None:
            result = ListNode(p2.value)
        else:
            result.next = ListNode(p2.value)
        p2 = p2.next

    return result