【LeetCode】203. 移除链表元素（简单）——代码随想录算法训练营Day03

题目链接：203. 移除链表元素

题目描述

给你一个链表的头节点?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：直接在原链表移除元素

思路：直接在原来的链表上移除元素，需要分别考虑删除头节点和删除中间节点两种情况。删除中间节点只需要将其前一个节点指向其后一个节点，删除头节点需要将头节点的指针指向头节点的下一个节点。

/**
 * 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 && head.val === val) {
        head = head.next;
    }

    // 判断此时链表为空链表的情况
    if (head === null) {
        return null;
    }
 
    // 删除非头节点
    let cur = head;
    while (cur.next) {
        if (cur.next.val === val) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }
 
    return head;
};

分析：删除链表元素的过程中完整遍历了整个链表，时间复杂度为 O(n)，空间复杂度为 O(1)。

题解2：虚拟头节点

思路：给链表头节点前加上一个虚拟头节点，删除真正头节点的方法就和删除中间节点方法一样了，就可以统一删除逻辑。

/**
 * 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) {
    let vHead = new ListNode(0, head); // 创建虚拟头节点

    let cur = vHead; // 遍历起点为虚拟头节点
    while (cur.next) {
        if (cur.next.val === val) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }

    return vHead.next; // 返回真正的头节点
};

分析：删除链表元素的过程中同样完整遍历了整个链表，时间复杂度为 O(n)，空间复杂度为 O(1)。

收获

虚拟头节点是一种很巧妙的思想，使用虚拟头节点可以统一删除头节点和删除中间节点的逻辑，简化代码逻辑。