203-移除链表元素

标签：递归链表

题目信息

题目内容：

javascript

给你一个链表的头节点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

示例1图片如下:

题解

解法一

思路：

先判断head节点是否是满足条件的节点，如果是就删除，直到head节点不满足为止
设置一个遍历节点curNode，默认指向head节点，因为head节点已经确定不用删除，所以判断curNode.next.val是否等于val，如果等于，就将curNode.next指向curNode.next.next即可
直到curNode.next === null或者curNode.next.next === null就结束遍历
最后返回head节点即可

代码实现：

javascript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    // 先判断头节点是否有满足条件需要删除的
    while(head !== null && head.val === val) {
        head = head.next
    }
    let curNode = head
    while(curNode !== null && curNode.next !== null) {
        if(curNode.next.val === val) {
            curNode.next = curNode.next.next
            continue
        }
        curNode = curNode.next
    }
    return head
};

解法二

思路：

解法一需要先判断head节点是否需要删除，解法二不需要
创建一个虚拟头dummyHead节点，该节点的next指向链表的头节点head，这样全部的判断都可以使用同样的规则
设置一个遍历节点curNode，默认为dummyHead，遍历链表，当curNode.next不为null时，判断curNode.next.val是否等于val
如果相等，就将curNode.next设置为curNode.next.next，否则curNode = curNode.next
最后返回dummyHead的next即可

TIP

设置dummyHead后，所有的比较都直接比较curNode.next.val和val的关系即可，统一比较逻辑，不用额外担心边界条件

代码实现：

javascript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    const dummyHead = new ListNode(null, head)
    let curNode = dummyHead
    while(curNode.next !== null) {
        if(curNode.next.val === val) {
            curNode.next = curNode.next.next
            continue
        }
        curNode = curNode.next
    }
    return dummyHead.next
};

203-移除链表元素 #

题目信息 #

题解 #

解法一 #

解法二 #

203-移除链表元素

题目信息

题解

解法一

解法二