讲解下如何删除线性链表中数据域为item的所有结点
时间: 2023-05-29 07:06:03 浏览: 128
要删除线性链表中数据域为item的所有结点,可以使用双指针法来遍历链表并删除符合条件的结点。
具体步骤如下:
1. 定义两个指针p和q,初始时p指向链表头结点,q指向p的前驱结点。
2. 从头结点开始遍历链表,如果当前结点的数据域等于要删除的item,则删除该结点。删除时需要注意修改前驱结点的next指针,将其指向当前结点的后继结点,同时释放当前结点的内存空间。
3. 继续遍历链表,直到p指向链表尾结点为止。在遍历过程中,如果发现当前结点的数据域等于item,则执行删除操作;否则将p和q向后移动一个结点。
4. 删除完所有符合条件的结点后,返回删除后的链表头结点。
下面是示例代码:
```python
def delete_node(head, item):
# 定义双指针p和q
p = head.next
q = head
# 遍历链表
while p is not None:
# 如果当前结点的数据域等于item,则删除该结点
if p.data == item:
q.next = p.next
del p
p = q.next
else:
q = p
p = p.next
# 返回删除后的链表头结点
return head
```
需要注意的是,代码中的head为链表头结点,而不是第一个实际结点,因此从head.next开始遍历链表。此外,删除操作时需要使用del语句释放内存空间,否则会造成内存泄漏。
阅读全文