203.移除链表元素

• 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def removeElements(self, head, val):""":type head: Optional[ListNode]:type val: int:rtype: Optional[ListNode]"""dummy = ListNode(-1)# 定义哑节点（dummy node），方便处理头节点被删除的情况dummy.next = head# 哑结点的指针指向headcurrent = dummy# 创建一个current指针指向哑结点# 遍历链表while current.next:if current.next.val == val:# 若current所指的节点的下一个节点的元素值等于valcurrent.next = current.next.next# 把current所指节点的next区域指向下下个节点else:# 继续向前current = current.nextreturn dummy.next

• 时间复杂度：O(n), n为链表长度, 需要遍历链表中的每一个节点
• 空间复杂度：O(1)