题目描述：
解题思路：
由单链表的特殊性，如果删除的是头节点应该怎么操作呢？
这里就涉及如下链表操作的两种方式：
- 直接使用原来的链表进行删除操作
- 设置一个虚拟头节点进行删除操作
第一种操作：
移除头节点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头节点没有前一个节点。那么头节点应该如何移除呢，只需要将头节点向后移动一位就好，这样就从链表中移除了一个头节点。
这样就移除了一个头节点，在单链表中移除头节点和移除其他节点的操作方式是不同的，需要单独写一段逻辑来处理头节点的情况。那么可不可以以一种统一的逻辑来移除链表的节点呢。
其实可以设置一个虚拟头节点，这样原链表的所有节点就可以按照统一的方式移除了。
依旧还是在这个链表中，移除元素1.
这里来给链表添加一个虚拟头节点作为新的头节点，此时要移除这个旧头节点元素1。
在题目中，return头节点的时候，应该return dummyNode->next，这才是新的头节点。
解题过程：
第一种解法：设置虚拟头节点，删除头节点不需要单独考虑
class Solution: def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: dummy_head = ListNode(next=head) cur = dummy_head while(cur.next!=None): if(cur.next.val==val): cur.next = cur.next.next else: cur = cur.next return dummy_head.next
时间复杂度为O(n)，需要遍历链表一次；空间复杂度O(1)，因为是在原链表的基础上修改。
第二种解法：删除头节点时另作考虑，因为头节点没有前一个节点
class Solution: def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: while(head!=None and head.val==val): # 删除值相同的头节点后，可能新的头节点也相等，用循环解决 head = head.next if(head==None): return head prev = head while(prev.next!=None): if(prev.next.val==val): prev.next = prev.next.next else: prev = prev.next return head
第三种解法：递归
链表具有递归的性质，常可以递归实现。对于给定的链表，首先对除头节点head之外的节点进行删除操作，然后判断head的节点值是否等于给定的val。如果head的节点值等于val，则head需要被删除，因此删除之后的头节点为head.next；如果head的节点值不为val，则head保留，因此删除操作后的头节点还是head。上述过程是一个递归的过程。
递归的终止条件是head为空，此时直接返回head。当head不为空时，递归地进行删除操作，然后判断head的节点值是否等于val并决定是否要删除head。
class Solution: def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: if head is None: # 终止条件 return head head.next = self.removeElements(head.next, val) # head的下一个节点只需要指向递归过的结果就好 if head.val == val: return head.next else: return head
时间复杂度为O(n)，递归过程中需要遍历链表一次；空间复杂度为O(n)，主要取决于递归调用栈，最多不会超过n层。