7-2 两个有序链表序列的交集
时间: 2024-06-07 18:12:21 浏览: 30
对于两个有序链表序列的交集,可以使用双指针的方法来求解。假设两个链表分别为链表A和链表B。
1. 初始化两个指针,分别指向链表A和链表B的头节点。
2. 遍历链表A和链表B,比较两个指针所指向节点的值:
- 如果节点A的值小于节点B的值,则将指针A向后移动一位。
- 如果节点B的值小于节点A的值,则将指针B向后移动一位。
- 如果节点A和节点B的值相等,则将该值添加到结果链表中,并将指针A和指针B都向后移动一位。
3. 重复步骤2,直到其中一个链表遍历完毕。
最后,返回结果链表即可得到两个有序链表序列的交集。
相关问题
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;
}
};
1-7 两个有序链表序列的交集
根据引用和引用的描述,输入的格式应为两行,每行分别是一个由若干个正整数构成的非降序序列,用-1表示序列的结尾。数字之间用空格间隔。
对于这个问题,我们需要找到两个有序链表的交集。根据引用中的描述,我们需要输出交集序列,数字之间用空格分开,结尾不能有多余空格;若交集为空,输出NULL。
根据题目给出的两个有序链表序列,我们可以通过比较两个链表的元素来找到它们的交集。
下面是求解交集的一种方法:
1. 定义两个指针分别指向两个链表的头部。
2. 初始化一个空的结果链表。
3. 当两个指针都不为空时,进行以下操作:
a. 如果两个指针指向的元素相等,将该元素添加到结果链表中,并且两个指针都向后移动一位。
b. 如果第一个指针指向的元素小于第二个指针指向的元素,将第一个指针向后移动一位。
c. 如果第一个指针指向的元素大于第二个指针指向的元素,将第二个指针向后移动一位。
4. 返回结果链表。
根据这个方法,我们可以得到1-7两个有序链表序列的交集。