7-3 两个有序链表序列的交集 (20 分)

### 回答1：
题目描述

给定两个递增排序的链表，本题要求将两个链表中相同的元素输出为新的递增排序链表。

输入格式

输入分别在两行中给出两个递增排序的链表，每个链表的格式为：

第一行：N1 v1->v2->…->vN1
第二行：N2 w1->w2->…->wN2
其中N1和N2（≤N1,N2≤10^5）是链表长度，vi和wi（−10^9≤vi,wi≤10^9）分别是链表中的元素。链表结点的地址从第1到N1/N2编号。

输出格式

在一行中输出两个输入链表的交集，按递增排序。若无交集则输出NULL。

输入样例1

3 1->2->3
5 1->2->3->4->5
输出样例1

1->2->3
输入样例2

3 1->3->5
5 2->4->6->8->10
输出样例2

NULL

算法1

(链表遍历) $O(n)$

1.将两个链表遍历一遍，将相同的元素存储在一个新的链表中。
2.将新的链表按递增排序。

时间复杂度

两个链表遍历一遍，时间复杂度为O(n)。

C++ 代码

算法2

(双指针) $O(n)$

1.将两个链表遍历一遍，将相同的元素存储在一个新的链表中。
2.将新的链表按递增排序。

时间复杂度

两个链表遍历一遍，时间复杂度为O(n)。

C++ 代码

### 回答2：
题目描述：

给定两个升序排列的链表序列A和B，输出A和B的交集，每个元素只输出一次。

输入格式：

输入分为两部分：第一部分是第一个链表的长度N，第二部分是第一个链表的元素；第三部将是第二个链表的长度M，第四部分是第二个链表的元素。每个元素为一个32位有符号整数。

输出格式：

输出分为两部分：第一部分为交集的元素个数K；第二部分为K个整数，表示交集元素。

输入样例1：

5 1 3 4 7 9
4 2 3 5 7
输出样例1：

2 3 7
输入样例2：

5 1 2 3 4 5
5 1 2 3 4 5
输出样例2：

5 1 2 3 4 5

解题思路：

按顺序遍历两个链表A和B，如果A的当前值小于B的当前值，A的指针往后移动，反之则B的指针往后移动。当两个链表当前值相等时，将他们的当前值加入结果集，并分别移动两个指针。

代码实现：

### 回答3：
题目描述：

给定两个递增的有序单向链表序列，找出它们的交集并输出。

思路分析：

由于链表是有序的，所以可以通过比较节点的值来找出它们的交集。创建一个新的链表，每次从两个链表中取出较小的节点，并将它添加到新链表中，直到任意一个链表为空为止，此时新链表即为它们的交集。具体算法如下：

1. 创建一个新的链表 result

2. 定义两个指针，分别指向两个链表的头节点，一个为 l1，一个为 l2

3. 循环遍历两个链表，如果其中一个链表为空，则跳出循环

4. 比较 l1 和 l2 的值，如果 l1 的值小，则将 l1 添加到 result 中，并将 l1 后移一位；否则将 l2 添加到 result 中，并将 l2 后移一位

5. 返回新链表 result

代码实现：

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
struct ListNode* p1 = headA;
struct ListNode* p2 = headB;
struct ListNode* result = NULL;
struct ListNode* tail = NULL;

while (p1 != NULL && p2 != NULL) {
if (p1->val < p2->val) {
p1 = p1->next;
}
else if (p1->val > p2->val) {
p2 = p2->next;
}
else {
if (result == NULL) {
result = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
tail->val = p1->val;
}
else {
tail->next = (struct ListNode*)malloc(sizeof(struct ListNode));
tail = tail->next;
tail->val = p1->val;
}
p1 = p1->next;
p2 = p2->next;
}
}

if (tail != NULL) {
tail->next = NULL;
}

return result;
}

总结：

本题通过比较两个有序链表的值，能够高效地找出它们的交集。同时，我们还需要注意链表节点的创建和释放，以避免内存泄漏的问题。