# 0203. 移除链表元素 ## 题目地址(203. 移除链表元素) <https://leetcode-cn.com/problems/remove-linked-list-elements/> ## 题目描述 ``` <pre class="calibre18">``` 删除链表中等于给定值 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) ## 公司 - 阿里 - 腾讯 - 百度 - 字节 ## 思路 这个一个链表基本操作的题目，思路就不多说了。 ## 关键点解析 - 链表的基本操作（删除指定节点） - 虚拟节点 dummy 简化操作 > 其实设置 dummy 节点就是为了处理特殊位置（头节点），这这道题就是如果头节点是给定的需要删除的节点呢？ 为了保证代码逻辑的一致性，即不需要为头节点特殊定制逻辑，才采用的虚拟节点。 - 如果连续两个节点都是要删除的节点，这个情况容易被忽略。 eg: ``` <pre class="calibre18">``` <span class="hljs-title">// 只有下个节点不是要删除的节点才更新 current</span> <span class="hljs-keyword">if</span> (!next || next.val !== val) { current = next; } ``` ``` ## 代码 - 语言支持：JS，Python Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {ListNode} head * @param {number} val * @return {ListNode} */</span> <span class="hljs-keyword">var</span> removeElements = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">head, val</span>) </span>{ <span class="hljs-keyword">const</span> dummy = { next: head } <span class="hljs-keyword">let</span> current = dummy; <span class="hljs-keyword">while</span>(current && current.next) { <span class="hljs-keyword">let</span> next = current.next; <span class="hljs-keyword">if</span> (next.val === val) { current.next = next.next; next = next.next; } <span class="hljs-keyword">if</span> (!next || next.val !== val) { current = next; } } <span class="hljs-keyword">return</span> dummy.next; }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-title"># Definition for singly-linked list.</span> <span class="hljs-title"># class ListNode:</span> <span class="hljs-title"># def __init__(self, x):</span> <span class="hljs-title"># self.val = x</span> <span class="hljs-title"># self.next = None</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removeElements</span><span class="hljs-params">(self, head: ListNode, val: int)</span> -> ListNode:</span> prev = ListNode(<span class="hljs-params">0</span>) prev.next = head cur = prev <span class="hljs-keyword">while</span> cur.next: <span class="hljs-keyword">if</span> cur.next.val == val: cur.next = cur.next.next <span class="hljs-keyword">else</span>: cur = cur.next <span class="hljs-keyword">return</span> prev.next ``` ``` **复杂度分析** - 时间复杂度：O(N)O(N)O(N) - 空间复杂度：O(1)O(1)O(1) 更多题解可以访问我的LeetCode题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经37K star啦。 关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。