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

好的，以下是代码实现：

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* merge(ListNode* S1, ListNode* S2) {
    if (!S1) return S2;
    if (!S2) return S1;
    ListNode* head = new ListNode(0);
    ListNode* cur = head;
    while (S1 && S2) {
        if (S1->val <= S2->val) {
            cur->next = S1;
            S1 = S1->next;
        } else {
            cur->next = S2;
            S2 = S2->next;
        }
        cur = cur->next;
    }
    cur->next = S1 ? S1 : S2;
    return head->next;
}

int main() {
    ListNode* S1 = new ListNode(1);
    S1->next = new ListNode(3);
    S1->next->next = new ListNode(5);
    ListNode* S2 = new ListNode(2);
    S2->next = new ListNode(4);
    S2->next->next = new ListNode(6);
    ListNode* S3 = merge(S1, S2);
    while (S3) {
        cout << S3->val << " ";
        S3 = S3->next;
    }
    return 0;
}