已知两个链表 A 和 B 分别表示两个集合,其元素递增排列。请设计 算法求出 A 与 B 的交集,并存放于 A 链表中。
时间: 2023-05-15 18:07:23 浏览: 75
可以使用双指针法来解决这个问题。首先,我们定义两个指针 pA 和 pB 分别指向链表 A 和 B 的头节点。然后,我们比较 pA 和 pB 指向的节点的值,如果它们相等,说明这个节点是 A 和 B 的交集元素,我们将这个节点加入到结果链表中,并将 pA 和 pB 都向后移动一位。如果 pA 指向的节点的值小于 pB 指向的节点的值,说明 A 中的元素比 B 中的元素小,我们将 pA 向后移动一位。反之,如果 pA 指向的节点的值大于 pB 指向的节点的值,说明 B 中的元素比 A 中的元素小,我们将 pB 向后移动一位。重复上述步骤,直到 pA 或 pB 为空为止。最后,返回结果链表即可。
以下是示例代码:
void intersection(ListNode* A, ListNode* B) {
ListNode* pA = A;
ListNode* pB = B;
ListNode* result = new ListNode(0);
ListNode* pResult = result;
while (pA != nullptr && pB != nullptr) {
if (pA->val == pB->val) {
pResult->next = new ListNode(pA->val);
pResult = pResult->next;
pA = pA->next;
pB = pB->next;
} else if (pA->val < pB->val) {
pA = pA->next;
} else {
pB = pB->next;
}
}
A = result->next;
}