已知两个带头结点的单链表A 和B 分别表示两个集合,元素值递增有序,设计算法求出A,B 的差集C,并同样以递增的形式存储。
时间: 2023-05-12 10:03:23 浏览: 89
设A和B是两个单链表,其表中元素递增有序
5星 · 资源好评率100%
可以使用双指针的方法,分别遍历两个链表,比较节点的值大小,如果A链表的当前节点值小于B链表的当前节点值,则将A链表的指针向后移动一位;如果A链表的当前节点值大于B链表的当前节点值,则将B链表的指针向后移动一位;如果A链表的当前节点值等于B链表的当前节点值,则将A、B链表的指针都向后移动一位。最后,将A链表中剩余的节点全部加入到C链表中即可。
以下是示例代码:
```
ListNode* getDifference(ListNode* A, ListNode* B) {
ListNode* C = new ListNode(0); // 创建C链表的头结点
ListNode* p = C; // 指向C链表的尾节点
ListNode* pa = A->next; // 指向A链表的第一个节点
ListNode* pb = B->next; // 指向B链表的第一个节点
while (pa != nullptr && pb != nullptr) {
if (pa->val < pb->val) {
p->next = new ListNode(pa->val);
p = p->next;
pa = pa->next;
} else if (pa->val > pb->val) {
pb = pb->next;
} else {
pa = pa->next;
pb = pb->next;
}
}
while (pa != nullptr) {
p->next = new ListNode(pa->val);
p = p->next;
pa = pa->next;
}
return C;
}
```
阅读全文