已知一个带头结点的循环链表为list,设计一个算法,删除链表中数据域值为item的所有结点,代码是什么
时间: 2024-10-22 10:29:44 浏览: 31
带头结点循环单链表-数据结构讲义
在循环链表中删除所有值为 `item` 的节点,需要特别处理头节点和循环条件。这里是一个简单的 Python 示例,假设 `ListNode` 类表示链表节点:
```python
class ListNode:
def __init__(self, data=0, next=None):
self.data = data
self.next = next
def delete_nodes_with_value(head, item):
# 初始化指针
current = head
prev = None
found = False
while True:
if current.data == item:
if not found: # 首次找到item,更新found状态
found = True
else: # 删除当前节点
if prev is None: # 如果前一个节点为空,说明是头节点
new_head = current.next if current.next != head else None
else:
prev.next = current.next
del current
else:
prev = current
current = current.next
# 检查是否达到尾部并再次指向头部
if current == head and found: # 循环链表情况
break
# 使用示例
# 创建一个循环链表,例如: head -> 1 -> 2 -> 3 -> 1 (形成环)
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = head
delete_nodes_with_value(head, 2) # 删除值为2的节点后,链表变为: head -> 1 -> 3 -> 1
```
阅读全文