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

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

给定两个递增排序的链表，本题要求将两个链表中的公共部分输出。

输入格式：

输入分2行，分别在每行给出由若干个正整数构成的递增链表，每个正整数用空格分开。数字和链表的长度N (1≤N≤10^5)，数字大小不超过10^6。

输出格式：

在一行中输出两个输入链表的公共部分，数字间以空格分开，但行末不能有多余空格。

输入样例：

3 4 5 6
2 4 6 8 10

输出样例：

4 6

解题思路：

本题需要输出两个有序链表的交集，可以使用双指针的方法，分别指向两个链表的头结点，然后比较两个指针所指向的节点的值，如果相等，则输出该值，并将两个指针都向后移动一位，否则将值较小的指针向后移动一位，直到其中一个链表遍历完为止。

代码实现：

### 回答2：
这道题要求我们找到两个有序链表的交集。由于链表已经是有序的，我们可以采用双指针的方法来遍历两个链表。

我们定义两个指针，p1 和 p2，分别指向两个链表的头结点。然后，我们依次比较两个指针指向的节点的值，如果相等，说明这个节点是两个链表的交集元素，我们将它保存下来，并让两个指针都往后移动一位；如果p1指向的节点的值小于p2指向的节点的值，那么p1往后移动一位，否则p2往后移动一位。不断重复这个过程，直到其中一个链表被遍历完为止。

下面是具体的代码实现：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    p1, p2 = headA, headB
    ans = []
    while p1 and p2:
        if p1.val == p2.val:
            ans.append(p1.val)
            p1 = p1.next
            p2 = p2.next
        elif p1.val < p2.val:
            p1 = p1.next
        else:
            p2 = p2.next
    return ans

时间复杂度：O(m+n)

空间复杂度：O(min(m,n))

可以看出，该算法时间复杂度为O(m+n)，其中m和n分别是两个链表的长度。因为我们从头到尾遍历了两个链表，并且每个节点最多被访问一次，所以时间复杂度为O(m+n)。空间复杂度为O(min(m,n))，因为我们只需要保存交集元素。因此，我们可以得出，这个算法是比较优秀的。

### 回答3：
题目描述：
给定两个递增序列 A 和 B ，请编写算法输出它们的交集序列。

输入格式：
第一行输入序列 A 的长度 N（0≤N≤10^5）；第二行输入由 N 个非负整数组成的递增序列 A 的元素；
第三行输入序列 B 的长度 M（0≤M≤10^5）；第四行输入由 M 个非负整数组成的递增序列 B 的元素；

输出格式：
输出由两个序列的交集组成的非递减序列，数字之间用一个空格隔开。若这两个序列的交集为空，则输出空行。注意，需要去除重复元素。

解题思路：
将两个数组都存放到 map 中，key 为数值，value 为出现次数。遍历两个 map，若有相同 key，取 value 小的放入结果数组中，并将两个 map 对应 key 的 value 减小相应的值。最终将结果数组按从小到大排序输出。

代码实现：