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