Description
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.
Examples:
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: []Solution in Python
Python
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
# Create a dummy node that points to the head of the list
# This helps in cases where the head itself needs to be removed
dummy = ListNode(0)
dummy.next = head
# Initialize current node to the dummy node
current = dummy
# Traverse the list until the end
while current.next is not None:
if current.next.val == val:
# If the next node's value is the target value, skip the next node
current.next = current.next.next
else:
# Otherwise, move to the next node
current = current.next
# Return the new head, which is the next of the dummy node
return dummy.nextDetailed Explanation
- Dummy Node Creation:
- A dummy node is created and points to the
headof the list. The dummy node is a common technique to simplify handling edge cases, particularly when theheaditself needs to be removed.
- A dummy node is created and points to the
- Current Pointer Initialization:
- We initialize a
currentpointer to the dummy node. This pointer will be used to traverse the list.
- We initialize a
- Traversing the List:
- We use a
whileloop to traverse the list untilcurrent.nextisNone, which indicates the end of the list. - Inside the loop, we check if
current.next.valis equal to the target value (val):- If it is, we skip the node by setting
current.nexttocurrent.next.next. This effectively removes the node with the target value from the list. - If it is not, we simply move the
currentpointer to the next node in the list.
- If it is, we skip the node by setting
- We use a
- Returning the New Head:
- After traversing and potentially removing nodes, the new head of the list is
dummy.nextbecausedummywas initially pointing to the original head. - This step ensures that if the original head was removed, the new head is correctly returned.
- After traversing and potentially removing nodes, the new head of the list is
Solution in Javascript
JavaScript
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function(head, val) {
// Create a dummy node that points to the head of the list
// This helps handle cases where the head itself needs to be removed
let dummy = new ListNode(0);
dummy.next = head;
// Initialize a pointer to traverse the list
let current = dummy;
// Traverse the list until the end
while (current.next !== null) {
if (current.next.val === val) {
// If the next node's value is equal to the target value, skip it
current.next = current.next.next;
} else {
// Otherwise, move to the next node
current = current.next;
}
}
// Return the new head, which is the next of the dummy node
return dummy.next;
};Solution in Java
Java
class Solution {
public ListNode removeElements(ListNode head, int val) {
// Create a dummy node that points to the head of the list
// This helps handle cases where the head itself needs to be removed
ListNode dummy = new ListNode(0);
dummy.next = head;
// Initialize a pointer to traverse the list
ListNode current = dummy;
// Traverse the list until the end
while (current.next != null) {
if (current.next.val == val) {
// If the next node's value is equal to the target value, skip it
current.next = current.next.next;
} else {
// Otherwise, move to the next node
current = current.next;
}
}
// Return the new head, which is the next of the dummy node
return dummy.next;
}
}Solution in C#
C#
public class Solution {
public ListNode RemoveElements(ListNode head, int val) {
// Create a dummy node that points to the head of the list.
// This helps handle cases where the head itself needs to be removed.
ListNode dummy = new ListNode(0);
dummy.next = head;
// Initialize a pointer to traverse the list.
ListNode current = dummy;
// Traverse the list until the end.
while (current.next != null) {
if (current.next.val == val) {
// If the next node's value is equal to the target value, skip it.
current.next = current.next.next;
} else {
// Otherwise, move to the next node.
current = current.next;
}
}
// Return the new head, which is the next of the dummy node.
return dummy.next;
}
}