1-7 两个有序链表序列的交集

根据引用和引用的描述，输入的格式应为两行，每行分别是一个由若干个正整数构成的非降序序列，用-1表示序列的结尾。数字之间用空格间隔。

对于这个问题，我们需要找到两个有序链表的交集。根据引用中的描述，我们需要输出交集序列，数字之间用空格分开，结尾不能有多余空格；若交集为空，输出NULL。

根据题目给出的两个有序链表序列，我们可以通过比较两个链表的元素来找到它们的交集。
下面是求解交集的一种方法：

1. 定义两个指针分别指向两个链表的头部。
2. 初始化一个空的结果链表。
3. 当两个指针都不为空时，进行以下操作：
a. 如果两个指针指向的元素相等，将该元素添加到结果链表中，并且两个指针都向后移动一位。
b. 如果第一个指针指向的元素小于第二个指针指向的元素，将第一个指针向后移动一位。
c. 如果第一个指针指向的元素大于第二个指针指向的元素，将第二个指针向后移动一位。
4. 返回结果链表。

根据这个方法，我们可以得到1-7两个有序链表序列的交集。

相关问题

7-7 两个有序链表序列的交集

这个问题可以使用双指针的方法来解决。我们可以分别遍历两个链表，比较当前节点的值，如果相等则将该节点加入结果链表中，否则将值较小的节点的指针向后移动一位。当任意一个链表遍历完毕时，交集的查找也就结束了。

以下是代码实现：

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
    while p1 and p2:
        if p1.val == p2.val:
            return p1
        elif p1.val < p2.val:
            p1 = p1.next
        else:
            p2 = p2.next
    return None

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 减小相应的值。最终将结果数组按从小到大排序输出。

代码实现：