# 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啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。