Delete Nodes From Linked List Present in Array - Leetcode 3217 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. So today, let's solve the problem delete nodes from linked list present in an array. So I'll keep this one nice and short. The idea is we're given a linked list that might look like this. We're also given an array of numbers. If any of these nodes has a value that exists within that array, we want to remove that node from the linked list. And so in this case, we would remove all three of these and then return the remaining linked list. It could be empty. I mean, it could technically be null. It could be non-mpy. And if it's non- empty, of course, we want to return the original nodes. We want to return the head of the remaining list. How do we go about solving this problem? Well, the first thing that you need to do is how do we do the lookup? How do we know if this value exists in there? We can do a linear scan. We can go through that entire thing either by looping over it or using a built-in function. But since it's an array, it's going to be linear time. Lookups though are quicker with hash data structures. Whether it's a hashmap or in this case a hash set is going to be sufficient. So that's exactly what we're going to do. The lookup in that case will go from O of N to constant time. So the algorithm is going to be this. Go through each node. If the value exists in the hash set, we will convert this into a hash set. then remove the node. Okay, so now you might be wondering how do we go about removing a node. Well, the first thing I want to tell you is that there is a trick with link list problems. You almost always want to have a dummy node when you're modifying a linked list. It makes the code just a little bit easier. Let me show you what I mean. Like this example here, if we were updating this linked list, we'd say that, okay, well, right now we have a pointer. This is the head of the linked list, and we are now trying to delete it. Okay, so since this is the head, we should probably change the head pointer to now be at the next node. But if we were removing a node from the middle, suppose this one down here, like this is our head right now. We're not removing the head. We're removing the node after the head. So in that case, we just want to take this pointer and then shift it over there. So we can remove the difference between both of these by doing something called a dummy node. The edge case comes from the fact that we could remove from the beginning of the list. So let's just create a random node. Doesn't really matter what the value is. I'll say it's zero. And let's set the next pointer to the head of the existing link list. Now, we're going to do the exact same thing as before. This is a one, so let's remove it. How do we do that? Well, one possible way is to use two pointers. Keep track of the previous node and keep track of the current node. And if the current node is something we want to delete, then take the previous next pointer and set it to current.next. That's pretty much going to remove it. And then in this particular case, the previous pointer should stay here. It should not be shifted. Our current pointer should only be shifted here. Because if we shift both of the pointers, if we put the previous pointer over here and the current pointer over here, we're going to consider removing this one. We're going to check, okay, is this a value we want to remove? And then we'll end up removing it. But we ended up skipping this guy. So that's why you don't want to shift the previous pointer if you deleted the node. Okay, but what if we don't delete the node? Suppose we weren't deleting this one. Well, then we would shift both of the pointers. Then we would shift previous by one and we would shift current by one. And then, you know, do the same thing here. So, that's more or less how you go about solving the problem. I think we're actually ready to code this up very quickly. Let's go over the time and space. We're given two inputs. The size of them is not necessarily going to be the same. Let's say this is n. Let's say this is m. So, overall the time complexity, we're going to convert this into a hash and we're going to iterate over the entire link list. That's going to be n plus m space. We are using a data structure. the hash set, remember? So that's going to be bigo of N. Now, let's code it up. So the first thing I'm going to do is just take nums and convert it into a hash set. I'm able to do this in Python because there's no like static typing. You might not be able to do that in your own language. You might have to create a new variable name. Um, but now let's do the dummy node. Let's create a random node. And let's give it a value of zero. It doesn't really matter what value we give it. Let's set the next pointer though to the head of the given linked list here. And now let's basically do that two-pointer thing I was talking about having the previous pointer set to uh the dummy node initially and then the current pointer set to the head or we could say dummy.ext but it doesn't really matter. They're both the same. And now we say while current because current is the node that we're considering to delete. And so we're going to check if the current.val is in the nums hash set then we want to delete it. And that's very easy to do. We just say previous.n next is equal to current.n next. And remember in this case we don't shift the previous pointer. We don't want to do that. We don't want to skip a node. We only shift the current pointer. So say current is now going to be current.ext. Now the alternative is where we don't delete the node. In that case it's pretty simple. We just shift both of the pointers. So previous will be previous next. Current will be current.ext. You might notice that there is a duplicate line in both of these conditions. It doesn't really matter in a real interview. I personally wouldn't care that much, but it does make the code a little bit better. So, I'm going to go ahead and move this line out of the if statement and then delete this one. Lastly, at the end, we are going to return dummy.next. If we ended up deleting every single node in the linked list, what would dummy do.next point to? It would probably point to null. If we didn't delete every single node, it's going to point to the new head of the linked list. because even though we're deleting nodes, we're never changing the order of them. So this is the whole solution. Let's run it. As you can see, it works. It's pretty efficient. You can actually solve this problem without keeping track of two pointers. You can get away with just using one pointer. So let's do that. I guess I'll leave it as previous. And then instead of current, I'm going to say previous.n next because we know that current was always one ahead of previous anyway. For current here, I'm going to change that again to previous.next. And to current here, I'm also going to change it to previous.next. So now this is just, you know, being shifted by one. Here I'm going to change this to previous next. And same thing here. Actually, I think I'm going a little bit too much on autopilot because we don't need to shift all of these. So let me delete this line and just reread what we're doing here. So if the next node is one that we want to delete, let's delete it. Otherwise, just shift the pointer. I think that's actually enough. I don't think we actually need anything else since we only have one pointer anyway. And let me go ahead and run this. And you can see this one works as well. I don't think it's necessarily more efficient to be honest. Um, but the runtime says so. But if you found this helpful, check out necode.io for a lot more. I'm going to be launching a free newsletter pretty soon. It's going to be covering data structures, system design, and a lot more. I'll also be making a lot more system design videos pretty soon. I'm really excited about that. So subscribe if you want to see