## 题目地址(203. 移除链表元素)

https://leetcode-cn.com/problems/remove-linked-list-elements/

## 题目描述

```
删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

```

## 前置知识

- [链表](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md)

## 公司

- 阿里
- 腾讯
- 百度
- 字节

## 思路

这个一个链表基本操作的题目，思路就不多说了。

虽然题目比较简单，但是实际面试出现的频率却不低， 因此大家一定要能够写出 bug free 的代码才可以。

链表的题目 90% 的 bug 都出现在：

1. 头尾节点的处理
2. 指针循环引用导致死循环

因此大家对这两个问题要保持 100% 的警惕。

## 关键点解析

- 链表的基本操作（删除指定节点）
- 虚拟节点 dummy 简化操作

> 其实设置 dummy 节点就是为了处理特殊位置（头节点），这这道题就是如果头节点是给定的需要删除的节点呢？
> 为了保证代码逻辑的一致性，即不需要为头节点特殊定制逻辑，才采用的虚拟节点。

- 如果连续两个节点都是要删除的节点，这个情况容易被忽略。
  eg:

```js
// 只有下个节点不是要删除的节点才更新 current
if (!next || next.val !== val) {
  current = next;
}
```

## 代码

- 语言支持：JS，Python

Javascript Code:

```js
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function (head, val) {
  const dummy = {
    next: head,
  };
  let current = dummy;

  while (current && current.next) {
    let next = current.next;
    if (next.val === val) {
      current.next = next.next;
      next = next.next;
    }

    if (!next || next.val !== val) {
      current = next;
    }
  }

  return dummy.next;
};
```

Python Code:

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        prev = ListNode(0)
        prev.next = head
        cur = prev
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return prev.next
```

**复杂度分析**

- 时间复杂度：$O(N)$
- 空间复杂度：$O(1)$

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
