数据结构与算法

Question

用带头结点的单链表表示整数集合，完成以下算法并分析时间复杂度:
(1)设计一个算法求两个集合A和B的差集运算,即C=A－B.要求算法的空间复杂度为0(1).并释放单链表A和B中不需要的结点。
(2)假设集合中的元素按递增排列，设计一个高效算法求两个集合A和B的差集运算,即C＝A- B,要求算法的空间复杂度为0(1),并释放单链表A和B中不需要的结点。

Answer 1

第一个 就是遍历A，然后每个A的元素去B里面遍历一遍找，找到的话就从A里面减掉。
第二个就是两个指针分别取A和B的第一个元素，然后哪个指针指的数值小就加1继续比较，直到指的数值相等了，从A里面删掉相应元素，两个指针分别加1继续。