題目敘述
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
Example 1:
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
Example 2:
Input: head = [], val = 1
Output: []
Example 3:
Input: head = [7,7,7,7], val = 7
Output: []
Constraints:
- The number of nodes in the list is in the range
[0, 10**4].
1 <= Node.val <= 500 <= val <= 50
題目翻譯
給一個連結序列，從中刪除相同值的節點。
解法解析
這題的解法也是很基本的就是要遍歷所有的節點，跟題目 206 一樣，分別都會有迭代和遞迴的方式來解。主要是迭代的解法中，我們在前面多加一個 sentinel 節點，減少需要針對起始節點做判斷，今天如果起始節點是要刪除的元素的時候會比較麻煩。所以在開頭多加一個節點就可以把全部的序列都以同樣的條件去判斷和處理。
解法範例
Go
Recursive
func removeElements(head *ListNode, val int) *ListNode {
if head == nil {
return nil
}
head.Next = removeElements(head.Next, val)
if head.Val == val {
return head.Next
}
return head
}
Sentinel node
func removeElements(head *ListNode, val int) *ListNode {
var sentinel = &ListNode{Next: head}
var prev *ListNode = sentinel
var curr *ListNode = head
for curr != nil {
if curr.Val == val {
prev.Next = curr.Next
} else {
prev = curr
}
curr = curr.Next
}
return sentinel.Next
}
JavaScript
Recursive
var removeElements = function (head, val) {
if (!head) return null;
head.next = removeElements(head.next, val);
return head.val === val ? head.next : head;
};
Sentinel node
var removeElements = function (head, val) {
const sentinel = new ListNode(0, head);
let prev = sentinel,
curr = head;
while (curr) {
if (curr.val === val) {
prev.next = curr.next;
} else {
prev = curr;
}
curr = curr.next;
}
return sentinel.next;
};
Kotlin
Recursive
class Solution {
fun removeElements(head: ListNode?, `val`: Int): ListNode? {
if (head == null) return null
head.next = removeElements(head.next, `val`)
return if (head.`val` == `val`) head.next else head
}
}
Sentinel node
class Solution {
fun removeElements(head: ListNode?, `val`: Int): ListNode? {
var sentinel = ListNode(0)
sentinel.next = head
var prev = sentinel
var curr = head
while (curr != null) {
if (curr.`val` == `val`) {
prev.next = curr.next
} else {
prev = curr
}
curr = curr.next
}
return sentinel.next
}
}
PHP
Recursive
class Solution
{
function removeElements($head, $val)
{
if ($head == null) {
return null;
}
$head->next = $this->removeElements($head->next, $val);
return $head->val == $val ? $head->next : $head;
}
}
Sentinel node
class Solution
{
function removeElements($head, $val)
{
$sentinel = new ListNode(0, $head);
$prev = $sentinel;
$curr = $head;
while ($curr != null) {
if ($curr->val == $val) {
$prev->next = $curr->next;
} else {
$prev = $curr;
}
$curr = $curr->next;
}
return $sentinel->next;
}
}
Python
Recursive
class Solution:
def removeElements(self, head: ListNode | None, val: int) -> ListNode | None:
if head is None:
return None
head.next = self.removeElements(head.next, val)
return head.next if head.val == val else head
Sentinel node
class Solution:
def removeElements(self, head: ListNode | None, val: int) -> ListNode | None:
sentinel = ListNode(0, head)
prev, curr = sentinel, head
while curr:
if curr.val == val:
prev.next = curr.next
else:
prev = curr
curr = curr.next
return sentinel.next
Rust
Swift
Recursive
class Solution {
func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
guard head != nil else {
return nil
}
head!.next = removeElements(head!.next, val)
return head!.val == val ? head!.next : head
}
}
Sentinel node
class Solution {
func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
var sentinel = ListNode(0, head)
var prev = sentinel
var curr = head
while curr != nil {
if curr!.val == val {
prev.next = curr!.next
} else {
prev = curr!
}
curr = curr!.next
}
return sentinel.next
}
}