移除链表元素

题目

题目链接

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.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
输出： []

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

解题思路

该题目实际上就是删除链表中特定值的节点。

单链表删除节点的操作是将节点.next指向下下个节点，因此如果直接遍历当前节点的话，需要进行记忆当前节点的前一个节点。

😊虚拟头节点

对此，我们不妨换种思路，如果直接遍历当前节点的下一个节点则不必再去记忆当前节点的前一个节点，但同时会产生一个问题，就是如果当前单链表没有节点，则cur.next不存在。另外如果需要移除的节点是头节点，则操作比起删除其他节点会麻烦一些。解决办法是虚拟一个头节点。

解题代码

var removeElements = function(head, val) {
    let res = new ListNode(0,head); //避免head为空时，cur.next不存在以及删除头节点操作繁琐
    let cur = res;
    while(cur.next){
        if(cur.next.val === val){
            cur.next = cur.next.next;
            continue;
        }
        cur = cur.next;
    }
    return res.next;//虚拟头节点之后，结果需要去掉虚拟的头节点
};