203.remove-linked-list-elements.md

题目地址(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 

前置知识

• 链表

公司

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

思路

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

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

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

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

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

关键点解析

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

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

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

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

代码

• 语言支持：JS，Python，C++，Java

Javascript Code:

/** * @param {ListNode} head * @param {number} val * @return {ListNode} */varremoveElements=function(head,val){constdummy={next: head,};letcurrent=dummy;while(current&&current.next){letnext=current.next;if(next.val===val){current.next=next.next;next=next.next;}if(!next||next.val!==val){current=next;}}returndummy.next;};

Python Code:

# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution: defremoveElements(self, head: ListNode, val: int) ->ListNode: prev=ListNode(0) prev.next=headcur=prevwhilecur.next: ifcur.next.val==val: cur.next=cur.next.nextelse: cur=cur.nextreturnprev.next

C++ Code:

classSolution { public: ListNode* removeElements(ListNode* head, int val) { structListNode* dummyHead = newListNode(0, head); structListNode* temp = dummyHead; while (temp->next != NULL) { if (temp->next->val == val) { temp->next = temp->next->next; } else { temp = temp->next; } } return dummyHead->next; } };

Java Code:

classSolution { publicListNoderemoveElements(ListNodehead, intval) { ListNodedummyHead = newListNode(0); dummyHead.next = head; ListNodetemp = dummyHead; while (temp.next != null) { if (temp.next.val == val) { temp.next = temp.next.next; } else { temp = temp.next; } } returndummyHead.next; } }

复杂度分析

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

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

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