This is the 8th day of my participation in the August More Text Challenge. For details, see:August is more challenging
Topic Description:
203. Remove linked List elements – LeetCode (leetcode-cn.com)
Given a list with head and an integer val, remove all nodes in the list that satisfy node.val == val and return the new head Node.
The sample a
Input: the head =,2,6,3,4,5,6 [1], val = 6 output: [1, 2, 3, 4, 5]Copy the code
Example 2
Input: head = [], val = 1Copy the code
Example 3
Input: head = [7,7,7,7], val = 7Copy the code
Tip:
- The number of nodes in the list is in the range [0,104][0, 10^4][0,104]
1 <= Node.val <= 50
0 <= val <= 50
Thought analysis
The steps to delete a node
- Find the node before this node
- Deleting a file
Three methods
- Think twice when deleting a head node (because the head node has no previous node)
- Add a virtual head node, and remove the head node without additional consideration
- recursive
The iteration
We choose to add a virtual node to point to the head node, and then iterate over the list.
Use temp to represent the current node. If the next node of temp is not empty and the node value of the next node is equal to the given val, the next node needs to be deleted.
If the node value of the next node of Temp is not equal to the given val, the next node is retained and temp is moved to the next node.
When the next node of Temp is empty, the list traversal ends, and all nodes whose value is equal to val are deleted.
AC code
class Solution {
fun removeElements(head: ListNode? , `val` :Int): ListNode? {
Dummy = next; dummy = next; dummy = next
val dummy = ListNode(0)
dummy.next = head
var temp = dummy
while(temp.next ! =null) {
if (temp.next.`val` = = `val`) {
temp.next = temp.next.next
} else {
temp = temp.next
}
}
return dummy.next
}
}
Copy the code
recursive
First, the node after the head node is deleted. Finally, the head node may need to be deleted, so it is processed separately
AC code
class Solution {
fun removeElements(head: ListNode? , `val` :Int): ListNode? {
vartemp = head temp? .next = removeElements(temp? .next, `val`)
if(temp? . `val` = = `val`) {
returntemp? .next }else {
return temp
}
}
}
Copy the code
conclusion
It’s a very normal linked list operation
reference
Remove List Elements – Remove List Elements – Force link (LeetCode) (leetcode-cn.com)
203. Removing List Elements (Three Methods) – Removing List Elements – LeetCode (leetcode-cn.com)