已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。 输入格式: 输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。 输出格式: 在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。c/c++语言实现

以下是C++语言的实现代码：

#include <iostream>
using namespace std;

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

ListNode* getIntersection(ListNode* head1, ListNode* head2) {
    ListNode* dummy = new ListNode(-1);
    ListNode* tail = dummy;

    while (head1 != NULL && head2 != NULL) {
        if (head1->val == head2->val) {
            tail->next = new ListNode(head1->val);
            tail = tail->next;
            head1 = head1->next;
            head2 = head2->next;
        } else if (head1->val < head2->val) {
            head1 = head1->next;
        } else {
            head2 = head2->next;
        }
    }

    ListNode* ans = dummy->next;
    delete dummy;
    return ans;
}

int main() {
    ListNode* head1 = NULL;
    int x;
    while (cin >> x && x != -1) {
        ListNode* node = new ListNode(x);
        node->next = head1;
        head1 = node;
    }

    ListNode* head2 = NULL;
    while (cin >> x && x != -1) {
        ListNode* node = new ListNode(x);
        node->next = head2;
        head2 = node;
    }

    ListNode* head3 = getIntersection(head1, head2);

    if (head3 == NULL) {
        cout << "NULL" << endl;
    } else {
        while (head3 != NULL) {
            cout << head3->val << " ";
            head3 = head3->next;
        }
        cout << endl;
    }

    return 0;
}

输入样例：

1 2 3 4 5 6 -1
2 4 6 8 10 -1

输出样例：

6 4 2