LeetCode 203移除链表元素：我的解法为何失效？需用temp节点？

当输入链表为[1,2,6,3,4,5,6]、目标值为6时，我写的错误解法输出结果是[5]，而正确解法能得到符合预期的[1,2,3,4,5]。我疑惑为什么正确解法要用到temp节点，而不能像我一样直接返回prev？

正确解法 #

public static ListNode removeElements(ListNode head, int val) {
    ListNode temp = new ListNode(0);
    temp.next = head;
    ListNode prev = temp;
    while(head != null) {
        if(head.val == val) {
            prev.next = head.next;
        }
        else {
            prev = head;
        }
        head = head.next;
    }
    return temp.next;  
}

错误解法 #

public static ListNode removeElements_wrong(ListNode head, int val) {
    ListNode prev = new ListNode(0);
    prev.next = head;
    while(head != null) {
        if(head.val == val) {
            prev.next = head.next;
        }
        else {
            prev = head;
        }
        head = head.next;
    }
    return prev;  
}

问题分析 #

为什么返回prev会出错？ #

在错误解法里，prev是一个随遍历不断移动的节点：

• 当当前head不是目标值时，prev会移动到head的位置；
• 遍历结束后，prev最终停在链表的最后一个有效节点上（比如测试用例里的5）。
  返回prev本质上只返回了最后一个节点，而非整个处理后的链表头节点，这就是输出[5]的原因。

temp节点的作用是什么？ #

temp是虚拟头节点，核心作用有两个：

1. 统一处理头节点被删除的情况：如果原链表头节点就是目标值（比如输入是[6,1,2]），没有虚拟头节点的话，删除头节点的逻辑会和中间节点不一样，需要额外判断；有了temp后，头节点就和其他节点一样，可以通过prev.next修改，无需特殊处理。
2. 保留处理后的链表头节点入口：temp的位置从始至终固定，它的next指向处理后链表的真正头节点。不管遍历过程中prev怎么移动，最后返回temp.next就能拿到完整的处理后链表，而非某个中间或末尾节点。

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