链表中的经典问题——移除链表元素I

移除链表元素

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

 题解一，迭代法：

解题思路：

        1. 首先需要考虑，链表为空或head节点的值等于val的情况，这里可以引入一个虚拟的哑节点dummy_node，该哑节点指向头节点，引入哑节点的好处就是不用特殊考虑链表为空或头节点为空的情况。

        2. 定义一个current变量，指向哑节点dummy_node；

        3. 从current.next开始遍历，直到为None;

        4. 遍历过程中，分两种情况处理，当current.next.val==val时，那么需要删掉该节点，指向下一个节点；

        5. 当current.next.val!=val时，继续执行遍历

代码实现：

class Solution:
    def remove_elements(self,head:Optional(ListNode), val:int)-> Optional(ListNode):
        
        # 定义一个虚拟哑节点
        dummy_node = ListNode(0)
        
        # 将哑节点指向头节点
        dummy_node.next = head

        # 定义一个current变量指向哑节点
        current = dummy_node
           
        # 从current.next开始遍历
        while current.next:
            
            if current.next.val == val:
                # 这里current.next指向了新的节点，那dummy_node也重新指向新的头节点
                current.next = current.next.next
            else:
                # 继续遍历
                current = current.next
        
        return dummy_node.next

# 为什么没有返回head，而是返回的dummy_node.next，因为当head.val==val时，并没有删除头节点即head，但是current.next = current.next.next却更新了dummy_node.next，即新的头节点

题解二，递归法：

解题思路：

代码实现：

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if not head:
            return head 

        # 这里使用了递归调用 self.removeElements(head.next, val)，它的作用是删除链表中除头节点外值为 val 的节点。这个调用会不断地向链表的后面部分递归，直到链表的末尾。
        head.next = self.removeElements(head.next,val)

        if head.val==val:
            return head.next
        else:
            return head