两个有序链表序列的交集

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

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

1 2 5 -1
2 4 5 8 10 -1

输出样例:

2 5

// 引入输入输出流库
#include 
// 引入字符串库
#include 
// 使用标准命名空间
using namespace std;
 
// 定义链表节点结构体
typedef struct ListNode {
    // 节点值
    int val;
    // 下一个节点指针
    ListNode* next;
    // 构造函数，初始化节点值和下一个节点指针
    ListNode(int x) : val(x), next(NULL) {}
}ListNode_t;
 
// 定义三个链表节点指针
ListNode_t* s1, * s2, * s3;
 
// 输入函数，用于构建链表
ListNode_t* input() {
    // 节点值
    int val;
    // 头节点和当前节点指针
    ListNode_t* head, * p;
    head = p = NULL;
    // 输入节点值
    cin >> val;
    // 当节点值不为-1时，继续构建链表
    while (val != -1) {
        // 新建节点
        ListNode_t* node = new ListNode(val);
        // 如果当前节点为空，则将头节点和当前节点都指向新建节点
        if (p == NULL) {
            head = p = node;
        }
        // 否则，将当前节点的下一个节点指向新建节点，并将当前节点更新为新建节点
        else {
            p->next = node;
            p = p->next;
        }
        // 输入下一个节点值
        cin >> val;
    }
    // 返回头节点
    return head;
}
 
// 打印链表函数
void print(ListNode_t* head) {
    // 当前节点指针
    ListNode_t* p = head;
    // 如果头节点为空，则输出"NULL"
    if (p == NULL) {
        cout << "NULL" << endl;
        return;
    }
    // 否则，遍历链表并打印节点值
    while (p) {
        if (p && p->next)
            cout << p->val << " ";
        else
            cout << p->val;
        p = p->next;
    }
}
 
// 求交集函数
ListNode_t* intersection(ListNode_t* s1, ListNode_t* s2) {
    // 头节点和当前节点指针
    ListNode_t *head,*s3;
    head = s3 = NULL;
    // 当两个链表都不为空时，进行比较
    while (s1 && s2) {
        // 如果第一个链表的当前节点值大于第二个链表的当前节点值，则将第二个链表的当前节点向后移动
        if (s1->val > s2->val)
            s2 = s2->next;
        // 如果第一个链表的当前节点值小于第二个链表的当前节点值，则将第一个链表的当前节点向后移动
        else if (s1->val < s2->val)
            s1 = s1->next;
        // 如果两个链表的当前节点值相等，则将当前节点加入到交集链表中，并将两个链表的当前节点都向后移动
        else if(s1->val == s2->val){
            if (s3 == NULL) {
                head = s3 = s1;
            }
            else {
                s3->next = s1;
                s3 = s3->next;
            }
            s1 = s1->next;
            s2 = s2->next;
        }
    }
   
    // 返回交集链表的头节点
    return head;
}
 
// 主函数
int main() {
 
    // 输入两个链表
    s1 = input();
    s2 = input();
    // 求两个链表的交集
    s3 = intersection(s1,s2);
    // 打印交集链表
    print(s3);
 
    // 返回0，表示程序正常结束
    return 0;
}