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

R7-2 两个有序链表序列的交集

题目描述

给定两个按升序排列的有序链表序列，找出它们的交集。

例如，链表A={1，3，4，7，9}，链表B={2，3，5，7，8}，则它们的交集为{3，7}。

算法思路

由于两个链表都是有序的，因此可以使用双指针法，依次比较两个链表中的元素。如果两个指针指向的元素相等，则将该元素加入到结果链表中，并将两个指针同时向后移动一位；如果第一个指针指向的元素小于第二个指针指向的元素，则将第一个指针向后移动一位；如果第二个指针指向的元素小于第一个指针指向的元素，则将第二个指针向后移动一位。

时间复杂度：O(m+n)，其中m和n分别为两个链表的长度。

空间复杂度：O(1)。

C++ 代码

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
ListNode* pA = headA;
ListNode* pB = headB;
ListNode* res = NULL;
while(pA != NULL && pB != NULL){
if(pA->val == pB->val){
if(res == NULL){
res = new ListNode(pA->val);
}else{
res->next = new ListNode(pA->val);
res = res->next;
}
pA = pA->next;
pB = pB->next;
}else if(pA->val < pB->val){
pA = pA->next;
}else{
pB = pB->next;
}
}
return res;
}
};