已知两个链表a和b分别表示两个集合,其元素递增排列。请设计算法求出a与b的交集,并存放于a链表中
时间: 2023-04-29 19:02:51 浏览: 149
2_链表_求la和lb的交集_
5星 · 资源好评率100%
算法步骤如下:
1. 定义两个指针p1和p2,分别指向链表a和b的头结点。
2. 遍历链表a和b,比较p1和p2所指向的元素大小。
3. 如果p1所指向的元素小于p2所指向的元素,则p1指向下一个元素。
4. 如果p1所指向的元素大于p2所指向的元素,则p2指向下一个元素。
5. 如果p1和p2所指向的元素相等,则将该元素插入到新的链表c中,并同时将p1和p2指向下一个元素。
6. 遍历完a和b后,将链表c中的元素复制到链表a中。
代码实现如下:
```python
def intersection(a, b):
p1, p2 = a.head, b.head
c = LinkedList()
while p1 and p2:
if p1.data < p2.data:
p1 = p1.next
elif p1.data > p2.data:
p2 = p2.next
else:
c.append(p1.data)
p1 = p1.next
p2 = p2.next
a.clear()
for item in c:
a.append(item)
```
其中,LinkedList为链表类,head为头结点,append方法为在链表尾部添加元素,clear方法为清空链表。
阅读全文