给一个链表的头结点head和一个整数val,请你清除链表中所有满足Node.val==val的节点并返回新的头结点
时间: 2024-09-15 12:03:13 浏览: 45
要清除链表中所有满足节点值等于给定整数`val`的节点,我们可以通过迭代的方式遍历链表,同时维护两个指针,一个用于遍历(我们称之为`current`),另一个用于记录前一个节点(我们称之为`prev`),以便正确地移除满足条件的节点。具体的步骤如下:
1. 创建一个哑节点`dummy`,它将作为结果链表的头结点,这样可以简化边界条件的处理。哑节点的`next`指针指向原始链表的头结点`head`。
2. 初始化`prev`为`dummy`,`current`为`head`。
3. 进行迭代,遍历整个链表。在每次迭代中:
- 如果`current`不为空且`current`的值等于`val`,则将`prev.next`指向`current.next`,从而移除`current`节点。
- 如果`current`不为空但其值不等于`val`,则`prev`移动到`current`。
- `current`向前移动到下一个节点。
4. 遍历完成后,返回哑节点的下一个节点,即为新的链表头结点。
以下是该算法的Python代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeElements(head, val):
dummy = ListNode(0)
dummy.next = head
prev, current = dummy, head
while current:
if current.val == val:
prev.next = current.next
else:
prev = current
current = current.next
return dummy.next
```
阅读全文