链表元素移除：移除指定值节点并返回链表新头节点

需求描述 #

给定链表的头节点head和整数val，移除链表中所有Node.val等于val的节点，并返回新的头节点。

提交的代码实现 #

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
      # 检查头节点是否为空
        if (head == None):
            return head
        
        prev = head
        curr = head
        while curr:
            if curr.val == val:
                if curr == prev:
                    head = head.next
                    prev = prev.next
                   
                else:
                    prev.next = curr.next
            else:
            
                if curr != prev:
                    prev = prev.next
            curr = curr.next
            return head

代码问题分析 #

这段代码存在致命逻辑错误：return head被写在while循环内部，导致循环仅执行一次就直接返回结果，根本无法遍历完整链表完成所有目标节点的移除操作。

修正后的代码实现 #

我们可以引入虚拟头节点简化头节点的特殊处理逻辑，修正后的代码如下：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # 创建虚拟头节点，统一头节点与中间节点的处理逻辑
        dummy_head = ListNode(next=head)
        current = dummy_head
        
        while current.next is not None:
            if current.next.val == val:
                # 移除目标节点
                current.next = current.next.next
            else:
                # 指针正常后移
                current = current.next
        
        # 返回虚拟头节点的下一个节点，即新的链表头
        return dummy_head.next

修正逻辑说明 #

• 虚拟头节点dummy_head的引入，避免了单独判断头节点是否为空、是否需要移除的复杂分支，让所有节点的移除逻辑保持一致。
• 遍历过程中通过current.next判断目标节点，确保指针修改不会出现断链问题。
• 将return语句移至循环结束后，保证完整遍历整个链表，移除所有符合条件的节点。

内容的提问来源于stack exchange，提问作者Goyam Jain