BUT BUT BUT, in the dummy node approach you will have to use O(n) space as you store the valid LL in the dummy LL, so, Striver's approach is the same, in which you fiddle with the links with TC - O(n) and SC - O(1)
@@suryapratapchaurasiya9198 the intuition is simple my friend, create a dummy node and then traverse through the original LL ok, and then in every iteration check if the node->data is equal to the key, if yes then dont append it to the dummy LL, if it is not equal append it to the dummy LL and in the end return the dummy->next as this will be the new LL head
@@anshpradhan1954 hey ansh i dont think we are creating new nodes every time in the dummy node approach.. we will be just pointing dummy.next to the node whose data not equal to key . so no extra space complexity would be involved with this approach . i believe striver want to provide solution in a more new way. space complexity will still be O(1) as we are creating a single dummy node
Updated the logic a bit. if you check the test cases, you would see that there are contiguous nodes with key hence, we can skip processing those nodes and directly jump to node where data is not equal to key Node curr = head; Node prevNode = curr.prev; while(curr != null){ if(curr.data == x){ prevNode = curr; // this is the node with key do{ curr = curr.next; }while(curr != null && curr.data == x); // update the ptrs when you get node where data != key if(prevNode.prev == null){ head = curr; }else{ prevNode.prev.next = curr; } // curr can be null eg. consider DLL 5-3-2-2-2-2-2 and key =2 if(curr != null){ curr.prev = prevNode.prev; } } if(curr!= null){ curr = curr.next; } } return head; TC -> O(N) SC -> O(1)
(Not for the java people) when i looked through comments I came across many dummy approach solutions but in my opinion there is something missing mostly in the C++ code that is if the temp==key then you need to delete the node and Yes, but should store the nextnode beforehand to move to the next node idk if am wrong or right but writing this because I thought that the main motive of the question was to delete the space took by the repititive nodes and somewhere we missed the point.👍
Hey guys we can use two pointers here starting from the head similarly like we did in the case of arrays to change the value in the node .it will be o(n) t.c and o(1) s.c .thankyou striver ❤.its because of u i got this approach into my mind
At 4:27 prevnode is moved from null to 4 ..but the condition for prev node to move forward is that prevnode!=null ... Here instead of being null the previous is moved to next .... Can anyone please help me😢 in understanding this ????
first of all it is not for moving it is for updating the links only we update the value of the prevnode in above lines "prevnode=temp->prev" there is no restriction to update the value of the prevnode, only a check before updating the links
my code ik it`s messier but still runs perfectly Node * deleteAllOccurrences(Node* head, int k) { // Write your code here while(head ->data == k){ Node* temp = head ; head = head -> next ; if(head == nullptr) return nullptr ; head -> prev = nullptr ; temp -> next = nullptr ; delete temp ; } Node* mover = head -> next ; while(mover){ if(mover -> data == k){ if(mover -> next == nullptr ){// only if tail also has data equal to the given key value Node* back = mover -> prev ; back -> next = nullptr ; mover -> prev = nullptr ; delete mover ; return head ; } else { Node* back = mover -> prev ; Node* front = mover -> next ; back -> next = front ; front -> prev = back ; Node* temp = mover ; mover = front ; temp -> next = nullptr ; temp -> prev = nullptr ; delete temp ; } } else mover = mover -> next ; } return head ; }
why you are not removing links after deletion like you did while teaching the deletion at kth index in Doubly Linked List? Can we us this same approach there also? I am trying to do that here but that's not working i don't know why..
Python Solution with Space Complexity: O(1) def deleteAllOccuranceOfX(head, x): temp = head if head is None: return None while(temp): next_pointer = temp.next if temp.data == x: #handle head if temp.prev is None: if head.next is None: return None temp.next.prev = None head = temp.next #handle tail elif temp.next is None: temp.prev.next = None else: temp.next.prev, temp.prev.next = temp.prev, temp.next temp = next_pointer return head
Dummy Node Approach: Node * deleteAllOccurrences(Node* head, int k) { //if head only null we cant do anything just return null if( head == nullptr) return nullptr; //taking dummy node and assign its next to head , back is null Node* dummy = new Node(-1 , head , nullptr); //head prev should me dummy now head->prev = dummy; //now traverse using cur until null Node* cur = head; while( cur != nullptr){ //cur is k if(cur->data == k){ //assign a prev and next ptr Node* prev = cur->prev; Node* nextNode = cur->next;
//now linking prev to next node, prev is always exist so no need to check prev->next = cur->next; //if next node is null , cant do NULL->prev , so check before linking backwards if(nextNode != nullptr )nextNode->prev = cur->prev; }
//now move cur , if cur element not equals it simply moves , if equals performs if and then moves, thats all. cur = cur->next;
![I.N "HALLUCINATION" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/n5B5q1Hwt_U/mqdefault.jpg)
Thank you striver for teaching us so well that every concept remains in the mind as everything is crystal clear.
Brother, update article because it will help us during revision
Dummy node approach will alot simpler and also intuitive.
can you provide the code and intution.
BUT BUT BUT, in the dummy node approach you will have to use O(n) space as you store the valid LL in the dummy LL, so, Striver's approach is the same, in which you fiddle with the links with TC - O(n) and SC - O(1)
@@suryapratapchaurasiya9198 the intuition is simple my friend, create a dummy node and then traverse through the original LL ok, and then in every iteration check if the node->data is equal to the key, if yes then dont append it to the dummy LL, if it is not equal append it to the dummy LL and in the end return the dummy->next as this will be the new LL head
@@anshpradhan1954 hey ansh i dont think we are creating new nodes every time in the dummy node approach.. we will be just pointing dummy.next to the node whose data not equal to key . so no extra space complexity would be involved with this approach . i believe striver want to provide solution in a more new way. space complexity will still be O(1) as we are creating a single dummy node
@@suryapratapchaurasiya9198
Node * deleteAllOccurrences(Node* head, int k) {
Node* dummyNode = new Node(-1);
Node* ptr = dummyNode;
Node* temp = head;
while(temp){
if(temp->data != k){
ptr->next = temp;
temp->prev = ptr;
ptr = temp;
}
else{
Node* delNode = temp;
delete delNode;
}
temp = temp->next;
}
ptr->next = NULL;
head = dummyNode->next;
delete dummyNode;
return head;
}
TC: O(n)
SC: O(1)
Updated the logic a bit.
if you check the test cases, you would see that there are contiguous nodes with key hence, we can skip processing those nodes and directly jump to node where data is not equal to key
Node curr = head;
Node prevNode = curr.prev;
while(curr != null){
if(curr.data == x){
prevNode = curr; // this is the node with key
do{
curr = curr.next;
}while(curr != null && curr.data == x);
// update the ptrs when you get node where data != key
if(prevNode.prev == null){
head = curr;
}else{
prevNode.prev.next = curr;
}
// curr can be null eg. consider DLL 5-3-2-2-2-2-2 and key =2
if(curr != null){
curr.prev = prevNode.prev;
}
}
if(curr!= null){
curr = curr.next;
}
}
return head;
TC -> O(N)
SC -> O(1)
Striver please bring a new series on heaps/stack and queque /strings or any other we're much awaited
(Not for the java people)
when i looked through comments I came across many dummy approach solutions but in my opinion there is something missing mostly in the C++ code that is if the temp==key then you need to delete the node and Yes, but should store the nextnode beforehand to move to the next node idk if am wrong or right but writing this because I thought that the main motive of the question was to delete the space took by the repititive nodes and somewhere we missed the point.👍
great video striver❤
God of DSA
thank youuu stiver!
Thank you
thankyou
Understood Bhaiya!
Thank You....
Understood Bhaiya thank you
Understood ✌✌
understood!!!
Java Code:
public class Solution {
public static Node deleteAllOccurrences(Node head, int k) {
// Write your code here.
Node temp =head;
while(temp!= null){
if(temp.data==k){
// to delete head
if(temp==head){
head= temp.next; // delete head
}
Node nextNode= temp.next;
Node prevNode = temp.prev;
if(nextNode!= null){
nextNode.prev= prevNode;
}
if(prevNode!= null){
prevNode.next= nextNode;
}
temp = nextNode;
}
else{
temp= temp.next;
}
}
return head;
}
}
Pliz update the article in a2z DSA sheet
Thank you Bhaiya
Hey guys we can use two pointers here starting from the head similarly like we did in the case of arrays to change the value in the node .it will be o(n) t.c and o(1) s.c .thankyou striver ❤.its because of u i got this approach into my mind
Lecture successfully completed on 29/11/2024 🔥🔥
Understood✅🔥🔥
At 4:27 prevnode is moved from null to 4 ..but the condition for prev node to move forward is that prevnode!=null ... Here instead of being null the previous is moved to next .... Can anyone please help me😢 in understanding this ????
first of all it is not for moving it is for updating the links only
we update the value of the prevnode in above lines "prevnode=temp->prev"
there is no restriction to update the value of the prevnode, only a check before updating the links
UNDERSTOOD;
Understood!
Understood ❤
Thank You✨
very easy dummy node approach
Node * deleteAllOccurrences(Node* head, int k) {
Node* dummynode = new Node(-1);
dummynode->next=head;
Node* temp=dummynode;
while(temp->next!=nullptr){
if(temp->next->data==k){
temp->next=temp->next->next;
if(temp->next!=nullptr)temp->next->prev=temp; //if tail element
}else temp=temp->next;
}
return dummynode->next;
}
Understood, thank you.
Bro , can we use predefined linkedlist or user-defined linkedlist in interview
Understood
my code ik it`s messier but still runs perfectly
Node * deleteAllOccurrences(Node* head, int k) {
// Write your code here
while(head ->data == k){
Node* temp = head ;
head = head -> next ;
if(head == nullptr) return nullptr ;
head -> prev = nullptr ;
temp -> next = nullptr ;
delete temp ;
}
Node* mover = head -> next ;
while(mover){
if(mover -> data == k){
if(mover -> next == nullptr ){// only if tail also has data equal to the given key value
Node* back = mover -> prev ;
back -> next = nullptr ;
mover -> prev = nullptr ;
delete mover ;
return head ;
}
else {
Node* back = mover -> prev ;
Node* front = mover -> next ;
back -> next = front ;
front -> prev = back ;
Node* temp = mover ;
mover = front ;
temp -> next = nullptr ;
temp -> prev = nullptr ;
delete temp ;
}
}
else mover = mover -> next ;
}
return head ;
}
understood sir
Thanks
//using dummy node java
func(head){
Node dummy =new Node(-1);
Node curr=dummy;
Node temp=head;
while(temp!=null)
{
if(temp.data!=k)
{
curr.next=temp;
temp.prev=curr;
curr=curr.next;
}
temp=temp.next;
}
//what if last node which is next to curr is k
curr.next=null;
return dummy.next;
}
why you are not removing links after deletion like you did while teaching the deletion at kth index in Doubly Linked List? Can we us this same approach there also? I am trying to do that here but that's not working i don't know why..
why we need to check for prevnode!=NULL ? since prevnode is always not NULL na? after the first node(head)?
Am i missing something?
understood
Python Solution with Space Complexity: O(1)
def deleteAllOccuranceOfX(head, x):
temp = head
if head is None:
return None
while(temp):
next_pointer = temp.next
if temp.data == x:
#handle head
if temp.prev is None:
if head.next is None:
return None
temp.next.prev = None
head = temp.next
#handle tail
elif temp.next is None:
temp.prev.next = None
else:
temp.next.prev, temp.prev.next = temp.prev, temp.next
temp = next_pointer
return head
amazing gurur ji
When we should expect the completion of this series?
Reorder a list problem explanation please
for the case where temp =head,why didnt u free up the old head after updation to new head??????
same question
Its because we are freeing the temp anyway after the if condition
It is deleted . Our temp =head .
So he moved head to head next .
But has removed temp was containing head
Thanks Bhaiya !!
hi are you engineering student
@@RaushanKumar-dt3pv yes
done myself with dummynode approach
❤
Dummy Node Approach:
Node * deleteAllOccurrences(Node* head, int k) {
//if head only null we cant do anything just return null
if( head == nullptr) return nullptr;
//taking dummy node and assign its next to head , back is null
Node* dummy = new Node(-1 , head , nullptr);
//head prev should me dummy now
head->prev = dummy;
//now traverse using cur until null
Node* cur = head;
while( cur != nullptr){
//cur is k
if(cur->data == k){
//assign a prev and next ptr
Node* prev = cur->prev;
Node* nextNode = cur->next;
//now linking prev to next node, prev is always exist so no need to check
prev->next = cur->next;
//if next node is null , cant do NULL->prev , so check before linking backwards
if(nextNode != nullptr )nextNode->prev = cur->prev;
}
//now move cur , if cur element not equals it simply moves , if equals performs if and then moves, thats all.
cur = cur->next;
}
//returning the new head.
return dummy->next;
}
Node list2 = new Node(-1);
Node t2 = list2;
Node temp = head;
while (temp != null) {
if (temp.data != x) {
t2.next = temp;
temp.prev = t2;
t2 = temp;
}
temp = temp.next;
}
t2.next = null;
return list2.next;
// just remove the -1 from the constructor then it will work on geeksforgeeks otherwise this approach is just fine
a little optimised version of java class Solution {
static Node deleteAllOccurOfX(Node head, int x) {
// Write your code here
while(head.data==x){
head=head.next;
if(head==null) return null;
}
//cutting the backward link
head.prev = null;
Node temp = head;
while(temp!=null){
if(temp.data==x){
Node nextNode = temp.next;
Node prevNode = temp.prev;
//make links
if(nextNode!=null) nextNode.prev = prevNode;
if(prevNode!=null) prevNode.next = nextNode;
//delete the links of temp
temp.next = null;
temp.prev = null;
temp = nextNode;
}
else temp = temp.next;
}
return head;
}
}
dummy list approach
c++;
Node * deleteAllOccurrences(Node* head, int k) {
Node* temp = head;
Node* dummyDll = new Node(-1);
Node* dummy = dummyDll;
while(temp != NULL){
if(temp->data != k) {
dummy->next = temp;
temp->prev = dummy;
temp = temp->next;
dummy = dummy->next;
}else{
temp = temp->next;
}
}
dummy->next = NULL;
Node* ans = dummyDll->next;
delete dummyDll;
return ans;
}
Node * deleteAtStart(Node* head, Node* temp, Node* curr) {
Node *newHead = head->next;
newHead->prev = nullptr;
delete head;
return newHead;
}
Node * deleteAtEnd(Node* head, Node* temp, Node* curr) {
temp->prev->next = nullptr;
delete temp;
return head;
}
Node * deleteAtMid(Node* head, Node* temp, Node* curr) {
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
delete temp;
return head;
}
Node * deleteAllOccurrences(Node* head, int k) {
Node *temp = head;
while (temp != nullptr) {
Node *curr = temp;
temp = temp->next;
if (curr->data == k) {
if (curr->prev == nullptr) {
head = deleteAtStart(head, curr, temp);
} else if (curr->next == nullptr) {
head = deleteAtEnd(head, curr, temp);
} else {
head = deleteAtMid(head, curr, temp);
}
}
}
return head;
}
Why is this giving runtime error in one of the test cases?
us
Java solution with handling idle nodes
//TC:O(N)
//SC:O(1)
static Node deleteAllOccurOfX(Node head, int x) {
Node temp=head;
while(temp!=null){
if(temp.data==x){
if(temp.prev==null){//head
Node before=head;
head=head.next;
if(head!=null){
head.prev=null;
}
before.next=null;
temp=head;
}
else{
Node before=temp.prev;
Node after=temp.next;
temp=temp.next;
if(after!=null){//tail
after.prev=before;
}
before.next=after;
}
}
else{
temp=temp.next;
}
}
return head;
}
27 jan 2025 10:02pm
Thank you Bhaiya
Understood
understood
Understood
thank u bhaiya
understood
thank you bhaiya
understood
Understood
Understood
understood
Understood
understood