Remove all elements from a linked list of integers that have value val.
1->2->6->3->4->5->6, val = 6
1->2->3->4->5
This is a really neat problem and there are two very interesting solutions to it. In this post, we're going to be looking at the iterative solution as it is most optimal, but I do think the recursive one is signficantly more intuitive.
You might approach this problem with one pointer where you simply iterate through and if you meet a bad value, delete it in place. However, you will quickly realize that the problem isn't quite that easy as the head can also be deleted.
You will idealy need three additional pointers. One pointer is going to be a container helper node, containing the head as it's next value. This is a node itself because that it either stores the head itself, or something that uses it as a pointer can discover the head for it and reflect that information over via referential equality.
The second pointer will be set equal to the helper node and it serves to re-assign it's .next head value to the first good node discovered. A good node is any node that doesn't need to be deleted.
The third pointer serves as the discovery iterator and also the iterative condition; we will continue to iterate for as long as it's not null.
Let's look at some examples.
sentinel = Dicussed Pointer 1
prev = Discussed Pointer 2
curr = Dicussed Pointer 3
1->2->6->3->4->5->6, val = 6
sentinel = x->1->2->6->3->4->5->6
prev = x->1->2->6->3->4->5->6
curr = 1->2->6->3->4->5->6
1->2->3->4->5
What's firstly important to note here is that head === sentinel.next === prev.next === curr.
In this example, sentinel.next is already a good node and also the head; in this case prev will simply serve to easily skip over bad nodes discovered by curr. Skipes made on prev will reflect over onto sentinel.next even though prev is being reassigned to curr incase of good nodes. This is because of the previously stated referential equality.
6->6->6->3->4->5->6, val = 6
sentinel = x->6->6->6->3->4->5->6
prev = x->6->6->6->3->4->5->6
curr = 6->6->6->3->4->5->6
3->4->5
In this example, since sentinel and prev are initially the same in memory object, as curr explores bad nodes, including the first one, prev.next will then point to curr.next in hopes that it will be a good node and it can find a node and reflect that over to sentinel and then on the next iteration, it will stop serving as a head pointer as it will then point to whatever curr would be.
Space: O(1)
The only additional variables created are pointer types.
Time: O(n)
The input linked list is only iterated over once.
function removeElements(head, val) {
const sentinel = new ListNode(0)
sentinel.next = head
let prev = sentinel
let curr = head
while (curr) {
if (curr.val === val) {
prev.next = curr.next
} else {
prev = curr
}
curr = curr.next
}
return sentinel.next
};