LeetCode 203移除链表元素：代码错误排查求助

问题描述 #

给定链表头节点head和目标值val，需要移除链表中所有值为val的节点。现有Java代码在处理测试用例[7,7,7,7]时，预期输出为空链表[]，但实际输出为[7,7,7]，需排查代码问题。

原代码 #

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null) return head;
        if(head.val==val) {head=head.next;}
        ListNode currentNode = head;
        ListNode previousNode = head;
        while(currentNode.val!=val) {
            previousNode=currentNode;
            currentNode = currentNode.next;
        }
        previousNode.next=currentNode.next;
        removeElements(currentNode.next,val);
        return head;
    }
}

问题分析 #

1. 首节点处理不彻底：原代码仅对首节点做了单次检查移除，当新的首节点依然等于val时（比如测试用例全为7的情况），没有继续处理，导致第一个7残留。
2. 空指针风险：当首节点被移为null后，后续currentNode = head会导致currentNode.val触发空指针异常；另外while(currentNode.val!=val)循环中，currentNode可能变为null，同样会引发空指针。
3. 递归逻辑无效：递归调用removeElements(currentNode.next,val)的返回值没有被赋值给任何变量，后续链表的修改无法反馈到当前的链表结构中，相当于白调用。
4. 循环逻辑缺陷：while(currentNode.val!=val)假设链表中一定存在值为val的节点，如果链表后续没有匹配节点，循环会一直走到currentNode为null，触发空指针。

修正方案 #

方案1：迭代实现（直观易调试） #

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 先移除头部所有匹配val的节点
        while (head != null && head.val == val) {
            head = head.next;
        }
        if (head == null) {
            return null;
        }
        ListNode prev = head;
        ListNode curr = head.next;
        // 遍历后续节点，移除匹配项
        while (curr != null) {
            if (curr.val == val) {
                prev.next = curr.next;
            } else {
                prev = curr;
            }
            curr = curr.next;
        }
        return head;
    }
}

方案2：递归实现（代码简洁） #

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        // 先递归处理后续节点，确保后续所有匹配节点都被移除
        head.next = removeElements(head.next, val);
        // 最后判断当前节点是否需要移除
        return head.val == val ? head.next : head;
    }
}

修正说明 #

• 迭代版本：先循环清理头部所有匹配节点，避免残留；遍历过程中全程做null检查，防止空指针；遇到匹配节点时通过修改前驱指针跳过当前节点，确保所有匹配项都被移除。
• 递归版本：利用递归特性从链表尾部向前处理，先确保后续节点的匹配项都被移除，再判断当前节点是否需要保留，逻辑简洁且无遗漏。

内容的提问来源于stack exchange，提问作者Ullas B.C