Remove a node in Linked List without traversing it
This might seem like clickbait but wait.. this isn’t!. It is a blog post explaining the problem https://leetcode.com/problems/delete-node-in-a-linked-list. If this wasn’t what you are looking for then, please turn back. If this is the one..then welcome!
This would be a part of the series of blogs which am writing for demystifying the underlying concepts of the most dreaded ( pun intended 😉 ) DSA problems. Stay tuned for more updates.
The Problem:
It seems simple at the first glance, delete a node in a linked list by value. But wait, that is where the twist comes in. We can’t go ahead with the normal way of traversing and deleting the node because we are not given the head of the list 😕.
So, how are we going to do it?? The normal approach fails as it can’t be done.
Approach:
One good thing given is that the node to be deleted is not at the end of the list.Why is this good?
Assume a linked list 1->2->3->4->5 according to the problem the node to be deleted won't be at the end which means it won't be 5 ( one less node to worry...whew! ) No,It doesn't mean we got one less node to worry but it means there will always be a node after the one to be deleted! [ The method which we are going to explain takes full advantage of this ]
So to delete the node we are going to take full advantage of the fact that there will always be nodes after it. This makes our job very easy! We are going to copy the next node’s value into the one to be deleted and then point it to the next node’s next.. 😐 I know this is confusing! Let me explain…
Explanation:
We have a linked list 1->2->3->4->5 so according to the question the node cannot be 5. So lets take the node to be deleted as 2So what we are going to do is,
Copy the node's next value into the current one.
2->3 will become 3->3.
We are not doing anything fancy, just copying the valuesGiven list: 1->2->3->4->5 New list: 1->3->3-4->5
Now’s, the fun part we are going to remove the actual 3 from the list and map the new node to 4. Still not getting it? Let us have a deeper look!
All we are doing is replacing the current node ( the one to be deleted ) with the next node’s value. Point the current node to the next node’s ( Actual here ) next, which means point the copied node in the diagram to the node with value 4.
And free the Actual node with value 3 if needed!
This is the logic to achieve deletion of the node in the linked list without traversing!
Hope you learned something from this.. stay tuned for more updates!
Happy learning
Btw, I got a git repo going for DSA Challenge which am undertaking to get a deeper understanding of DSA ( which I should have done when I was in college itself.. but hey no regrets in here! 😝 )
Link to the repo -> https://github.com/Yalamarthi97/DSA-Challenge
All comments and guidance will be taken gracefully without sitting in the corner and crying!
Love my blogs? It wasn’t possible without a steady input stream of hot coffee! Want to support me and help me write more blogs?? Buy me a cup of coffee https://www.buymeacoffee.com/SriharshaY and let the magic continue!
