删除链表中等于给定值 val 的所有节点
时间: 2024-09-12 15:09:55 浏览: 43
删除链表中等于给定值 `val` 的所有节点是一个常见的链表操作,通常会涉及到迭代或递归的方式来实现。这里是一种基本的迭代方法:
1. 定义两个指针,一个称为 `current`,用于遍历链表,另一个叫做 `prev`,用于记录 `current` 之前的位置。初始时,两者都指向链表的头结点。
2. 当 `current` 指向的节点值等于 `val` 时:
- 如果这是第一个节点(即 `prev` 为空),则需要创建一个新的链表头部。
- 否则,将 `prev` 的 `next` 指向 `current` 的下一个节点,跳过当前节点。
- 更新 `prev` 为 `current`,以便于处理下一个匹配的节点。
3. 遍历完链表后,如果最后一个节点被删除了(即 `current` 空),可能需要更新头结点。
下面是伪代码示例:
```python
def remove_nodes(head, val):
dummy = ListNode(0) # 创建虚拟头节点,方便处理头节点的情况
dummy.next = head
current = dummy
prev = None
while current is not None:
if current.val == val:
if prev is None: # 处理头节点
head = current.next
else:
prev.next = current.next
else:
prev = current
current = current.next
return dummy.next # 返回新链表的头节点
```
阅读全文