0203. 移除链表元素
题目地址(203. 移除链表元素)
题目描述
1
删除链表中等于给定值 val 的所有节点。
2
3
示例:
4
5
输入: 1->2->6->3->4->5->6, val = 6
6
输出: 1->2->3->4->5
Copied!
前置知识
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
这个一个链表基本操作的题目，思路就不多说了。
虽然题目比较简单，但是实际面试出现的频率却不低， 因此大家一定要能够写出 bug free 的代码才可以。
链表的题目 90% 的 bug 都出现在：
- 1.头尾节点的处理
- 2.指针循环引用导致死循环
因此大家对这两个问题要保持 100% 的警惕。
关键点解析
- 链表的基本操作（删除指定节点）
- 虚拟节点 dummy 简化操作
其实设置 dummy 节点就是为了处理特殊位置（头节点），这这道题就是如果头节点是给定的需要删除的节点呢？ 为了保证代码逻辑的一致性，即不需要为头节点特殊定制逻辑，才采用的虚拟节点。
- 如果连续两个节点都是要删除的节点，这个情况容易被忽略。eg:
1
// 只有下个节点不是要删除的节点才更新 current
2
if (!next || next.val !== val) {
3
current = next;
4
}
Copied!
代码
- 语言支持：JS，Python
Javascript Code:
1
/**
2
* @param {ListNode} head
3
* @param {number} val
4
* @return {ListNode}
5
*/
6
var removeElements = function (head, val) {
7
const dummy = {
8
next: head,
9
};
10
let current = dummy;
11
12
while (current && current.next) {
13
let next = current.next;
14
if (next.val === val) {
15
current.next = next.next;
16
next = next.next;
17
}
18
19
if (!next || next.val !== val) {
20
current = next;
21
}
22
}
23
24
return dummy.next;
25
};
Copied!
Python Code:
1
# Definition for singly-linked list.
2
# class ListNode:
3
# def __init__(self, x):
4
# self.val = x
5
# self.next = None
6
7
class Solution:
8
def removeElements(self, head: ListNode, val: int) -> ListNode:
9
prev = ListNode(0)
10
prev.next = head
11
cur = prev
12
while cur.next:
13
if cur.next.val == val:
14
cur.next = cur.next.next
15
else:
16
cur = cur.next
17
return prev.next
Copied!
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(1)$
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 1yr ago