【山西大学2022考研真题】已知递增有序的单链表 A,B,C 分别存储了一个集合,设计算法实现
A=A∪(B-C),要 求最终单链表 A 仍保持递增有序,结点定义如下:
(1)算法的基本思想如下:
1. 遍历链表A、B和C,使用三个指针分别指向当前节点。
2. 对于链表A中的每个节点,判断是否在链表B中出现,并且不在链表C中出现。
- 如果节点在B中出现且不在C中出现,将该节点从链表A中删除。
3. 将链表B中的节点插入到链表A中,并保持链表A的递增有序性。
(2)下面是使用C语言描述这个算法的代码:
typedef struct LNode {
int data;
struct LNode* next;
} LNode;
// 删除链表A中的节点
void deleteNode(LNode* prev, LNode* current) {
prev->next = current->next;
free(current);
}
// 将节点插入到链表A中
void insertNode(LNode* prev, LNode* current, LNode* node) {
node->next = current;
prev->next = node;
}
// 实现集合操作 A = (B-C) ∪ A
void setOperation(LNode* A, LNode* B, LNode* C) {
LNode* pa = A->next;
LNode* pb = B->next;
LNode* pc = C->next;
LNode* prev = A;
while (pa != NULL) {
if (pb != NULL && pb->data < pa->data) {
pb = pb->next;
} else if (pc != NULL && pc->data == pa->data) {
LNode* temp = pa;
pa = pa->next;
deleteNode(prev, temp);
pc = pc->next;
} else {
LNode* temp = pa;
pa = pa->next;
insertNode(prev, temp, pb);
prev = prev->next;
pb = pb->next;
}
}
// 将B中剩余的节点插入到A中
while (pb != NULL) {
LNode* temp = pb;
pb = pb->next;
insertNode(prev, temp, pb);
prev = prev->next;
}
}
(3)我们的算法需要对链表A、B和C进行遍历,时间复杂度为 O(n),其中 n 是链表的长度。算法的空间复杂度为 O(1),空间复杂度满足题目要求。