设计一个算法,求两个单链表表示的集合的交集,并将结果用一个新的单链表保存并返回
时间: 2023-04-30 07:01:32 浏览: 109
Linq两个List集合取交集的实现
5星 · 资源好评率100%
算法如下:
1. 定义一个新的单链表,用于保存交集结果。
2. 遍历第一个单链表,将其中的元素插入到一个哈希表中,以元素值为键,以节点指针为值。
3. 遍历第二个单链表,对于每个元素,如果在哈希表中存在,则将其插入到新的单链表中,并从哈希表中删除该元素。
4. 返回新的单链表作为结果。
时间复杂度为O(m+n),其中m和n分别为两个单链表的长度。
阅读全文