LeetCode: 203 Remove Linked List Elements

Given the head of a linked list and an integer val, remove all the nodes of the linked list that have Node.val == val, and return the new head.

Example

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
Explanation: We remove all the nodes with the value 6.

问题

给定一个链表的头节点 head 和一个整数 val，移除链表中所有值为 val 的节点，并返回新的头节点。

例子

输入: head = [1,2,6,3,4,5,6], val = 6
输出: [1,2,3,4,5]
解释: 我们移除了所有值为 6 的节点。

Iterative Solution

Approach: Iterative Approach with Dummy Node / 使用虚拟节点的迭代方法

To handle edge cases such as removing the head node, we can use a dummy node that points to the head of the list. We then iterate through the list and remove any nodes that have the value val.

Approach Explanation / 方法解释

Dummy Node: Create a dummy node that points to the head. This helps in handling cases where the head node itself needs to be removed.
Iterate Through the List: Use two pointers (prev and curr) to traverse the list. If curr.val == val, we adjust prev.next to skip the node.
Return the New Head: After processing the entire list, return dummy.next, which is the new head of the modified list.

Iterative Algorithm / 迭代算法

Create a dummy node that points to head.
Initialize prev as the dummy node and curr as head.
Traverse the list:
- If curr.val == val, skip the node by updating prev.next.
- Otherwise, move prev forward.
- Always move curr forward.
Return dummy.next.

Iterative Implementation / 迭代实现

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        # Create a dummy node that points to the head
        dummy = ListNode(0)
        dummy.next = head

        # Initialize pointers
        prev, curr = dummy, head

        # Traverse the list
        while curr:
            if curr.val == val:
                # Skip the current node
                prev.next = curr.next
            else:
                # Move prev to the current node
                prev = curr
            # Move to the next node
            curr = curr.next

        # Return the new head (dummy.next)
        return dummy.next

Iterative Solution Explanation / 迭代解决方案解释

Create Dummy Node / 创建虚拟节点
```
dummy = ListNode(0)
dummy.next = head
```
- English: We create a dummy node with a value of 0 that points to the head of the linked list. This helps handle edge cases where the head needs to be removed.
- Chinese: 我们创建一个值为 0 的虚拟节点，并指向链表的头节点。这有助于处理头节点需要被移除的边缘情况。
Initialize Pointers / 初始化指针
```
prev, curr = dummy, head
```
- English: We initialize prev to the dummy node and curr to the head of the list.
- Chinese: 我们将 prev 初始化为虚拟节点，将 curr 初始化为链表的头节点。
Iterate Through the List / 遍历链表
```
while curr:
```
- English: While curr is not None, we iterate through the list.
- Chinese: 当 curr 不是 None 时，我们遍历链表。
Skip Nodes with Value val / 跳过值为 val 的节点
```
if curr.val == val:
   prev.next = curr.next
```
- English: If the current node has the value val, we skip it by updating prev.next to point to curr.next.
- Chinese: 如果当前节点的值为 val，我们通过更新 prev.next 指向 curr.next 来跳过该节点。
Move Pointers / 移动指针
```
else:
   prev = curr
curr = curr.next
```
- English: If the current node does not have the value val, we move prev forward. In either case, we always move curr forward to the next node.
- Chinese: 如果当前节点的值不是 val，我们将 prev 向前移动。无论如何，我们总是将 curr 向前移动到下一个节点。
Return the New Head / 返回新头节点
```
return dummy.next
```
- English: After the loop finishes, we return dummy.next, which points to the new head of the list.
- Chinese: 循环结束后，我们返回 dummy.next，它指向链表的新头节点。

Recursive Solution

Approach: Recursive Approach / 递归方法

In the recursive approach, we process the nodes one at a time by calling the function on the next node until we reach the end of the list. Then, we decide whether to skip or keep the current node based on its value.

Recursive Algorithm / 递归算法

If head is None, return None (base case).
Recursively process the next node by calling self.removeElements(head.next, val).
Check if the current node’s value equals val:
- If yes, return head.next to skip the current node.
- If no, return the current node.

Recursive Implementation / 递归实现

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        # Base case: if the head is None, return None
        if not head:
            return None

        # Recursively call for the next node
        head.next = self.removeElements(head.next, val)

        # If current node's value equals val, skip it
        return head.next if head.val == val else head

Recursive Solution Explanation / 递归解决方案解释

Base Case: If Head is None / 基本情况：如果头节点为 None
```
if not head:
   return None
```
- English: If head is None, it means we’ve reached the end of the list, so we return None.
- Chinese: 如果 head 为 None，说明我们已经到达链表末尾，因此返回 None。
Recursive Call / 递归调用
```
head.next = self.removeElements(head.next, val)
```
- English: Recursively process the next node by calling removeElements on head.next.
- Chinese: 递归处理下一个节点，通过调用 removeElements 处理 head.next。
Check if Current Node Equals val / 检查当前节点是否等于 val
```
return head.next if head.val == val else head
```
- English: After processing the next node, check if the current node’s value is equal to val. If it is, skip the current node by returning head.next; otherwise, return head.
- Chinese: 在处理完下一个节点后，检查当前节点的值是否等于 val。如果相等，则通过返回 head.next 跳过当前节点；否则返回 head。

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(n), where n is the number of nodes in the linked list. Each node is processed once.
Space Complexity / 空间复杂度:
- Iterative Solution: O(1), since it only uses a few extra variables.
- Recursive Solution: O(n), due to the recursion stack, where n is the number of nodes.

Key Concept / 关键概念

Dummy Node / 虚拟节点: In the iterative solution, a dummy node simplifies the process of removing nodes, especially if the head needs to be removed.
Recursion / 递归: The recursive solution simplifies the logic by processing nodes one at a time and automatically handling the backtracking as recursion unwinds.

Summary / 总结

English: We can solve the problem of

removing linked list elements either iteratively using a dummy node and two pointers or recursively by processing each node and deciding whether to keep or skip it based on its value.
Chinese: 我们可以通过迭代方法使用虚拟节点和双指针，或通过递归处理每个节点并根据其值决定保留或跳过该节点来解决移除链表元素的问题。

Tips / 提示

English: For linked list problems, consider both iterative and recursive approaches, as recursion often provides a cleaner solution, but may use more space due to the recursion stack.
Chinese: 对于链表问题，可以考虑迭代和递归两种方法，因为递归通常提供更简洁的解决方案，但可能会由于递归栈使用更多空间。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: Practice linked list manipulation problems to understand the different techniques for iterating and modifying lists.
Chinese: 练习链表操作问题，以理解遍历和修改链表的不同技术。

Post Views: 8

CODEBITWAVE