已知两个链表a 和b分别表示两个集合,其元素递增增排列。请设计一个算法,用于求出 ^与b的交集,并存
时间: 2024-10-17 20:06:51 浏览: 34
这道题目可以使用双指针的方法来解决。我们可以定义两个指针p1和p2分别指向链表A和B的头结点,然后进行比较。如果p1指向的元素小于p2指向的元素,则p1向后移动一位;如果p1指向的元素大于p2指向的元素,则p2向后移动一位;如果p1指向的元素等于p2指向的元素,则将该元素加入到结果链表中,并且p1和p2都向后移动一位。最后返回结果链表即可。
具体实现可以参考以下代码:
```
void intersection(Linklist A, Linklist B) {
Linklist p1 = A->next, p2 = B->next, pre = A;
while (p1 && p2) {
if (p1->data < p2->data) {
pre = p1; p1 = p1->next;
} else if (p1->data > p2->data) {
Linklist tmp = p2;
p2 = p2->next;
free(tmp);
} else {
pre->next = p1;
pre = p1;
p1 = p1->next;
Linklist tmp = p2;
p2 = p2->next;
free(tmp);
}
}
pre->next = NULL;
}
```
阅读全文