Dare2Solve
Given the head of a singly linked list and an integer val
, the task is to remove all the nodes of the linked list that have val
as their value and return the new head of the list.
When removing elements from a linked list, especially when the nodes to be removed include the head, it's important to carefully adjust the pointers. The key is to iterate through the list while maintaining the integrity of the connections between nodes that do not need to be removed.
Handle Removal of Head Nodes:
val
. If it does, move the head pointer to the next node, effectively removing the current head. Repeat this process until the head no longer contains val
or the list becomes empty.Iterate Through the List:
curr
).val
.next
pointer of the current node to skip over the node with val
, effectively removing it from the list.Return the New Head:
O(n)
, where n
is the number of nodes in the linked list. Each node is visited exactly once.
O(1)
. The algorithm operates in-place, using only a constant amount of extra space.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
while (head && head->val == val) {
head = head->next;
}
ListNode* curr = head;
while (curr && curr->next) {
if (curr->next->val == val) {
curr->next = curr->next->next;
} else {
curr = curr->next;
}
}
return head;
}
};
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
while head and head.val == val:
head = head.next
curr = head
while curr and curr.next:
if curr.next.val == val:
curr.next = curr.next.next
else:
curr = curr.next
return head
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
while (head != null && head.val == val) {
head = head.next;
}
ListNode curr = head;
while (curr != null && curr.next != null) {
if (curr.next.val == val) {
curr.next = curr.next.next;
} else {
curr = curr.next;
}
}
return head;
}
}
var removeElements = function(head, val) {
while(head && head.val === val){
head = head.next
}
let curr = head
while(curr && curr.next){
if(curr.next.val === val){
curr.next = curr.next.next
}else{
curr = curr.next
}
}
return head
};