void intersectionList(List &LA, List LB) //用单链表求两个集合LA和LB的交集,结果在LA中
时间: 2024-10-24 08:11:14 浏览: 19
Android List(集合)中的对象以某一个字段排序案例
在使用单链表表示集合的情况下,`intersectionList`函数的主要目的是找到两个链表`LA`和`LB`中的公共元素,并将它们添加到`LA`中,同时保持`LA`的原始顺序。这个过程通常需要遍历两个链表,对于每个节点,检查它是否也存在于另一个链表中。
算法步骤可以大致概括如下:
1. 定义两个指针`p1`和`p2`分别指向`LA`和`LB`的头结点。
2. 遍历两个链表,如果遇到的节点值相等并且`LA`的指针未移动过(即`p1`没变),说明该节点是交集的一部分,将其从`LA`的下一个节点开始连接,直到找到`LB`链表结束或者`LA`链表再次有不相等的节点。
3. 更新`p1`和`p2`,继续遍历直到其中一个链表遍历完。如果`LA`的指针还在移动,那么剩下的部分就是`LA`独有的,不需要处理。
以下是伪代码形式:
```cpp
void intersectionList(List &LA, List LB) {
ListNode* p1 = LA.head;
ListNode* p2 = LB.head;
while (p1 && p2) {
if (p1->val == p2->val) {
// 添加到LA链表的剩余部分
insertToLA(LA, p1->next);
p1 = p2->next;
} else if (p1->val < p2->val) {
// LA已经遍历过这个节点,跳过
p1 = p1->next;
} else {
// LB已经遍历过这个节点,跳过
p2 = p2->next;
}
}
}
```
阅读全文