已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的并集新非降序链表S3。C++语言

可以使用双指针法来实现。具体步骤如下：

1. 定义三个指针，分别指向S1、S2、S3的头结点。
2. 比较S1和S2当前节点的大小，将较小的节点插入到S3中，并将指向该节点的指针后移一位。
3. 重复步骤2，直到S1或S2中的一个链表遍历完毕。
4. 将未遍历完的链表中的剩余节点插入到S3中。

以下是C++代码实现：

ListNode* merge(ListNode* S1, ListNode* S2) {
    ListNode* S3 = new ListNode(0);
    ListNode* p1 = S1;
    ListNode* p2 = S2;
    ListNode* p3 = S3;

    while (p1 != nullptr && p2 != nullptr) {
        if (p1->val <= p2->val) {
            p3->next = p1;
            p1 = p1->next;
        } else {
            p3->next = p2;
            p2 = p2->next;
        }
        p3 = p3->next;
    }

    if (p1 != nullptr) {
        p3->next = p1;
    }

    if (p2 != nullptr) {
        p3->next = p2;
    }

    return S3->next;
}