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;
}
};

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

对于两个有序链表序列的交集，可以使用双指针的方法来求解。假设两个链表分别为链表A和链表B。

1. 初始化两个指针，分别指向链表A和链表B的头节点。
2. 遍历链表A和链表B，比较两个指针所指向节点的值：
- 如果节点A的值小于节点B的值，则将指针A向后移动一位。
- 如果节点B的值小于节点A的值，则将指针B向后移动一位。
- 如果节点A和节点B的值相等，则将该值添加到结果链表中，并将指针A和指针B都向后移动一位。
3. 重复步骤2，直到其中一个链表遍历完毕。

最后，返回结果链表即可得到两个有序链表序列的交集。