已知两个非降序链表序列s1与s2，设计函数构造出s1与s2的交集新链表s3。\n\n输入格式:\n输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用

### 回答1： 空格分隔。题目保证所有数字不超过100，且每个序列中最多有105个数字。\n\n输出格式:\n在一行中输出两个序列的交集序列，数字间用空格分隔，结尾不能有多余空格。若新链表为空，输出NULL。\n\n输入样例:\n1 2 5 -1\n2 4 5 8 10 -1\n输出样例:\n2 5\n\n【题目分析】\n本题需要我们求两个非降序链表的交集，我们可以使用双指针的方法，分别遍历两个链表，比较两个链表当前指向的节点的值，如果相等，则将该节点加入新链表中，否则将值较小的指针向后移动一位，直到其中一个链表遍历完毕。\n\n【注意点】\n1. 需要注意链表为空的情况，此时需要输出NULL；\n2. 需要注意输出格式，结尾不能有多余空格。 ### 回答2： 这道题要求我们设计一个函数来构造出两个非降序链表序列的交集新链表。我们可以采用双指针的方式，从头开始扫描这两个链表，比较节点的值大小，将相同的节点连接在一起，最终得到的就是交集新链表。 具体步骤如下： 1.定义一个新的链表，作为交集新链表，用于存放相同的节点； 2.分别定义两个指针p1和p2，分别指向s1和s2的头节点； 3.遍历s1和s2的节点，比较节点的值大小，如果值相同，则将该节点连接到交集新链表s3的末尾，并将p1和p2往后移动一位； 4.如果p1指向的节点值小于p2指向的节点值，则将p1指针往后移一位； 5.如果p1指向的节点值大于p2指向的节点值，则将p2指针往后移一位； 6.一直重复步骤3到5，直到p1或者p2指向的节点为空。 最终得到的交集新链表s3，就是我们要求的结果。 但是需要注意的是，当s1或s2其中一个为空时，显然它们没有交集，这种情况需要特殊处理一下。 下面是代码实现： ``` #include <stdio.h> #include <stdlib.h> typedef struct node{ int data; struct node *next; }ListNode, *ListPtr; ListPtr FindCommonList(ListPtr head1, ListPtr head2); void InsertNode(ListPtr *head, int x); int main(){ ListPtr head1 = NULL; ListPtr head2 = NULL; ListPtr head3 = NULL; int x; printf("请输入第一个非降序链表：\n"); while (scanf("%d", &x) && x != -1){ InsertNode(&head1, x); } printf("请输入第二个非降序链表：\n"); while (scanf("%d", &x) && x != -1){ InsertNode(&head2, x); } head3 = FindCommonList(head1, head2); printf("交集新链表为："); ListPtr p = head3; while (p){ printf("%d ", p->data); p = p->next; } printf("\n"); return 0; } ListPtr FindCommonList(ListPtr head1, ListPtr head2){ ListPtr p1 = head1; ListPtr p2 = head2; ListPtr head3 = NULL; ListPtr p3 = NULL; while (p1 && p2){ if (p1->data == p2->data){ InsertNode(&head3, p1->data); p1 = p1->next; p2 = p2->next; } else if (p1->data < p2->data){ p1 = p1->next; } else { p2 = p2->next; } } return head3; } void InsertNode(ListPtr *head, int x){ ListPtr p = (ListPtr)malloc(sizeof(ListNode)); p->data = x; p->next = NULL; if ((*head) == NULL){ *head = p; } else { ListPtr q = *head; while (q->next){ q = q->next; } q->next = p; } } ``` 参考链接：https://blog.csdn.net/m0_53720225/article/details/114001526 ### 回答3： 本题需要对两个非降序链表进行求交集操作，考虑使用指针来实现链表的构造和遍历操作。 首先，定义链表节点的结构体，包含一个整数值和指向下一个节点的指针： ```C++ struct ListNode { int val; ListNode* next; ListNode(int _val) : val(_val), next(NULL) {} }; ``` 然后，读入两个非降序序列并分别构造对应的链表： ```C++ ListNode* buildList() { int val; cin >> val; ListNode* head = NULL; ListNode* tail = NULL; while (val != -1) { ListNode* node = new ListNode(val); if (head == NULL) { head = node; } else { tail->next = node; } tail = node; cin >> val; } return head; } ListNode* s1 = buildList(); ListNode* s2 = buildList(); ``` 接下来，考虑如何求两个链表的交集。由于两个链表是非降序的，因此可以使用类似归并排序的方法来遍历两个链表，并将相同的元素加入新链表中： ```C++ ListNode* s3 = new ListNode(0); ListNode* tail = s3; ListNode* p1 = s1; ListNode* p2 = s2; while (p1 != NULL && p2 != NULL) { 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; } } s3 = s3->next; ``` 最后，需要注意的是在遍历完成后，需要将新链表的头节点向后移动一位，将初始值0去掉。 完整的代码如下：