有一个整数单链表L,设计一个算法删除其中所有值为x的节点
时间: 2024-12-11 20:39:50 浏览: 13
当需要从整数单链表L中删除所有值为x的节点时,可以采用迭代的方式遍历链表。以下是步骤描述:
1. 定义两个指针,`prev` 和 `curr`,初始时都指向链表的头结点。
2. 遍历链表,对于每个当前节点 `curr`:
a. 如果 `curr` 的值等于 `x`,那么有三种情况:
- 如果 `curr` 是头结点,直接将头结点指向下一个非 `x` 节点(如果存在的话)。
- 否则,更新 `prev` 的 `next` 指向 `curr` 的下一个节点,然后释放 `curr`(因为不需要它了)。
3. 当 `curr` 不再为 `x` 或者到达链表末尾时,`prev` 就会是新的有效节点,继续移动到下一次循环。
4. 循环结束后,`prev` 指向的就是修改后的链表的头结点。
```python
def remove_x_from_list(head, x):
dummy = ListNode(0) # 创建一个虚拟头节点
dummy.next = head
prev = dummy
while curr := prev.next:
if curr.val == x:
prev.next = curr.next
else:
prev = curr
return dummy.next # 返回新头结点
```
在这个Python示例中,我们假设已经有一个`ListNode`类表示链表节点,`val`属性存储数值,`next`属性连接到下一个节点。`dummy`用于简化处理边界情况。
阅读全文