给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
解题思路
新增一个dummy节点,方便遍历和最后返回结果
p指针向后遍历,向前探一个节点,如果val相等,则需要跳过next节点
代码
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
dummy = ListNode()
dummy.next = head
p = dummy
while p is not None:
# 向前探一个节点检查是否等于val
if p.next and p.next.val == val:
# 跳过 p.next 节点
p.next = p.next.next
else:
p = p.next
return dummy.next
时间复杂度:O(n)
空间复杂度:O(1)