考研真题数据结构

（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)，空间复杂度满足题目要求。

?