L18. Delete all occurrences of a Key in DLL

Problem Link: tinyurl.com/yc...
Entire LL Sheet: takeuforward.o...
Check our A2Z DSA Course: takeuforward.o...
Please do give us a like, and subscribe to us if you are new to our channel.
Do follow us on our socials: linktr.ee/take...

[@alwayshemanthreddy]

Brother, update article because it will help us during revision

[@akashverma5756]

Dummy node approach will alot simpler and also intuitive.

[@suryapratapchaurasiya9198]

can you provide the code and intution.

[@anshpradhan1954]

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)

[@anshpradhan1954]

@@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

[@Shreyess_23]

Striver please bring a new series on heaps/stack and queque /strings or any other we're much awaited

[@mohitejaikumar]

God of DSA

[@TarunKumar-km5ps]

amazing gurur ji

[@user-rp2gn1qi6w]

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;
}
}

[@SurajKumar-ku1lg]

done myself with dummynode approach

[@tusharmishra2205]

great video striver❤

[@saileela3]

Thank you

[@ishanmoykhede9484]

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 ;
}

[@user-ql5pe3xc3p]

Bro , can we use predefined linkedlist or user-defined linkedlist in interview

[@user-ed8bc2hg5o]

understood

[@dynamictip5251]

//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;
}

[@oyeesharme]

thank you bhaiya

[@TON-108]

Understood Bhaiya!
Thank You....

[@ArpitaChoudhury_00]

Thank You✨

[@NazeerBashaShaik]

Understood, thank you.

[@user-tk2vg5jt3l]

Thank you Bhaiya

[@user-fw4kz3bb4g]

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;
}

[@aayushgakhar3525]

for the case where temp =head,why didnt u free up the old head after updation to new head??????

[@RaviKumar-sn6tu]

thank u bhaiya

[@subee128]

Thanks

[@YourCodeVerse]

Understood✅🔥🔥

[@user-ke7fs7ds6h]

understood sir

[@State_exam_preparation]

When we should expect the completion of this series?

[@dewanandkumar8589]

Understood

[@saidurgasrividyaupadhyayul4675]

Reorder a list problem explanation please

[@abhisweb2315]

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 ????

[@techtuber1344]

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;
}

[@rishitkamboj8078]

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

[@jayadeepmohanty5212]

[@priyanshkumar_iitd]

Thanks Bhaiya !!

[@RaushanKumar-dt3pv]

hi are you engineering student

[@priyanshkumar_iitd]

@@RaushanKumar-dt3pv yes

[@_sf_editz1870]

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;
}
}

[@harshavardhan7074]

❤

[@akshanshkaushal9422]

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;
}

[@priyamittal8302]

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?

[@cenacr007]

us

[@user-tk2vg5jt3l]

Thank you Bhaiya

[@hardikpatel352]

Understood

[@abhishekprasad010]

understood

[@sibiranganath]

Understood

[@chiragbansod8252]

understood

[@harshitjaiswal9439]

understood

[@ganeshvhatkar9253]

Understood