LeetCode203.移除链表元素

**移除链表元素**

###问题描述给定一个链表的头节点 `head` 和一个目标值 `val`,请你删除链表中所有值为 `val` 的节点,并返回修改后的链表。

### 示例示例1:

输入: `head = [1,2,6,3,4,5,6], val =6`

输出: `[1,2,3,4,5]`

示例2:

输入: `head = [], val =1`

输出: `[]`

示例3:

输入: `head = [7,7,7,7], val =7`

输出: `[]`

### 解决方案#### 方法一：递归法

# Definition for singly-linked list.
class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef removeElements(head, val):
 """
 Removes all nodes with value `val` from the linked list.

 Args:
 head (ListNode): The head of the linked list.
 val (int): The target value to be removed.

 Returns:
 ListNode: The modified linked list.
 """
 # Base case: If the list is empty, return None if not head:
 return None # Recursively remove nodes with value `val` from the rest of the list head.next = removeElements(head.next, val)

 # If the current node's value matches the target value, return the next node if head.val == val:
 return head.next # Otherwise, return the current node as the new head return head

#### 方法二：迭代法

def removeElements(head, val):
 """
 Removes all nodes with value `val` from the linked list.

 Args:
 head (ListNode): The head of the linked list.
 val (int): The target value to be removed.

 Returns:
 ListNode: The modified linked list.
 """
 # Create a dummy node to simplify the iteration process dummy = ListNode(0)
 dummy.next = head # Initialize two pointers, `prev` and `curr`, to the dummy node and the head of the list respectively prev = dummy curr = head # Iterate through the list until we reach the end while curr:
 # If the current node's value matches the target value, skip it by updating `prev.next`
 if curr.val == val:
 prev.next = curr.next else:
 # Otherwise, move `prev` and `curr` one step forward prev = curr curr = curr.next # Return the modified linked list (excluding the dummy node)
 return dummy.next

###代码注释* 在递归法中，我们首先检查链表是否为空。如果是，则返回 None。
* 然后，我们递归地从链表的下一个节点开始，直到找到不包含目标值的子链表。
* 如果当前节点的值与目标值匹配，则跳过该节点并继续向前移动。
* 在迭代法中，我们使用两个指针 `prev` 和 `curr` 来遍历链表。我们首先将 `dummy` 节点设置为链表的头部，以简化迭代过程。
* 然后，我们检查当前节点是否包含目标值。如果是，则跳过该节点并继续向前移动。
* 如果当前节点不包含目标值，则更新 `prev.next` 以指向下一个节点。

### 总结本文介绍了两种方法来移除链表中的元素：递归法和迭代法。递归法通过递归地从链表的下一个节点开始，直到找到不包含目标值的子链表来实现，而迭代法则使用两个指针 `prev` 和 `curr` 来遍历链表并跳过包含目标值的节点。两种方法都可以有效地移除链表中的元素，并返回修改后的链表。