请设计一段C语言算法。已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出A与B的交集,并存放于A链表中。
时间: 2023-04-01 13:03:21 浏览: 98
可以使用双指针法,分别指向链表A和B的头节点,比较两个节点的值,如果相等,则将该节点加入结果链表中,并同时向后移动两个指针;如果不相等,则将值较小的节点的指针向后移动一位。直到其中一个链表遍历完毕,最终得到的结果即为A与B的交集。
具体实现代码如下:
void intersection(ListNode* A, ListNode* B) {
ListNode* pA = A;
ListNode* pB = B;
ListNode* result = NULL;
ListNode* tail = NULL;
while (pA != NULL && pB != NULL) {
if (pA->val == pB->val) {
ListNode* node = new ListNode(pA->val);
if (result == NULL) {
result = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
pA = pA->next;
pB = pB->next;
} else if (pA->val < pB->val) {
pA = pA->next;
} else {
pB = pB->next;
}
}
// 将结果链表存放于A链表中
A->next = result;
}
阅读全文