已知两个链表A和B分别表示两个集合,其元素递增排列,请设计算法求出A与B的交集,并存放于A链表中
时间: 2024-03-19 10:18:21 浏览: 112
1. 定义两个指针pA和pB分别指向链表A和链表B的头节点。
2. 遍历两个链表,比较pA和pB指向的节点的值,如果相等,则将该节点加入结果链表中,并将pA和pB都指向下一个节点;如果pA指向的节点的值小于pB指向的节点的值,则将pA指向下一个节点;反之,将pB指向下一个节点。
3. 当其中一个链表遍历完毕时,结束循环。
4. 将结果链表中的元素复制到链表A中。
5. 返回链表A作为交集。
代码实现:
```
void intersection(ListNode* A, ListNode* B){
ListNode* pA = A->next;
ListNode* pB = B->next;
ListNode* result = new ListNode(0);
ListNode* p = result;
while(pA != nullptr && pB != nullptr){
if(pA->val == pB->val){
p->next = pA;
p = p->next;
pA = pA->next;
pB = pB->next;
}else if(pA->val < pB->val){
pA = pA->next;
}else{
pB = pB->next;
}
}
p->next = nullptr;
A->next = result->next;
}
```
阅读全文
相关推荐















