已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出两个集合A和B 的差集C
时间: 2024-03-19 08:15:39 浏览: 40
1. 初始化三个指针,分别指向链表A、B和C的头结点。
2. 遍历链表A和B,比较当前节点的值,如果A的值小于B的值,则将A的节点加入到C中,A指针后移;如果B的值小于A的值,则将B的节点丢弃,B指针后移;如果A和B的值相等,则丢弃两个节点,A和B指针同时后移。
3. 如果遍历完链表A后B还有剩余节点,将剩余节点加入到C中。
4. 返回链表C的头结点。
代码实现:
```
ListNode* getDifference(ListNode* A, ListNode* B) {
ListNode* C = new ListNode(0);
ListNode* pA = A;
ListNode* pB = B;
ListNode* pC = C;
while (pA != NULL && pB != NULL) {
if (pA->val < pB->val) {
pC->next = new ListNode(pA->val);
pA = pA->next;
pC = pC->next;
} else if (pA->val > pB->val) {
pB = pB->next;
} else {
pA = pA->next;
pB = pB->next;
}
}
while (pB != NULL) {
pB = pB->next;
}
return C->next;
}
```