91 lines
1.9 KiB
Markdown
91 lines
1.9 KiB
Markdown
|
## 题目地址
|
|||
|
|
https://leetcode.com/problems/remove-linked-list-elements/description/
|
|||
|
|
|
|||
|
|
## 题目描述
|
|||
|
|
```
|
|||
|
|
Remove all elements from a linked list of integers that have value val.
|
|||
|
|
|
|||
|
|
Example:
|
|||
|
|
|
|||
|
|
Input: 1->2->6->3->4->5->6, val = 6
|
|||
|
|
Output: 1->2->3->4->5
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 思路
|
|||
|
|
这个一个链表基本操作的题目，思路就不多说了。
|
|||
|
|
## 关键点解析
|
|||
|
|
|
|||
|
|
- 链表的基本操作（删除指定节点）
|
|||
|
|
- 虚拟节点 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
|
|||
|
|
```
|