两个有序链表序列的交集 分数 20 作者 DS课程组 单位 浙江大学 已知两个非降序链表序列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* getIntersectionNode(ListNode* head1, ListNode* head2) {
    ListNode* p1 = head1, *p2 = head2;
    ListNode* head = new ListNode(0); // 创建一个虚拟头节点
    ListNode* tail = head; // tail指向新链表的尾节点

    while (p1 && p2) {
        if (p1->val < p2->val) {
            p1 = p1->next;
        } else if (p1->val > p2->val) {
            p2 = p2->next;
        } else {
            tail->next = new ListNode(p1->val);
            tail = tail->next;
            p1 = p1->next;
            p2 = p2->next;
        }
    }

    return head->next; // 返回新链表的头节点
}

int main() {
    ListNode* head1 = new ListNode(1);
    head1->next = new ListNode(2);
    head1->next->next = new ListNode(3);
    head1->next->next->next = new ListNode(4);

    ListNode* head2 = new ListNode(2);
    head2->next = new ListNode(4);

    ListNode* head = getIntersectionNode(head1, head2);

    while (head) {
        cout << head->val << " ";
        head = head->next;
    }

    return 0;
}

在这个实现中，我们使用了一个虚拟头节点来简化代码，这个虚拟头节点的值可以是任意值，因为最终返回的是头节点的 next 指针。另外，我们还用 tail 指针来记录新链表的尾节点，这样就可以避免每次插入节点时都要遍历整个新链表找到尾节点。最后，记得释放掉动态申请的节点空间。