Remove Nodes From Linked List - Leetcode 2487 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem remove nodes from linked list we're going to go over two solutions for this problem it's not super crazy complicated we're given a linked list something that might look like this and basically we want to filter certain values from here and by filter I mean remove and the rule is if any value here five has a value anywhere to the right of it that happens to be greater than that five well then we skip it these two values both have 13 to the right of them 13 does not have any value to the right that's greater three has eight so we remove that eight does not have anything to the right of it at all so we keep these two and then that is the result ignoring the fact that this is a linked list when you think about this problem it's very classically a monotonic stack problem the idea is that think about if we had a list that was like 5 4 3 2 1 this is monotonic decreasing in this case equal matters like if this was 5 five and then 3 2 1 these two are equivalent I guess in the context of this problem because we're only going to remove a node if a value to the right is strictly greater than it not greater than or equal so equal in this case I guess is fine as well this is the main idea behind this problem now if we were to introduce another value to the right now suppose it's a two well that two is bigger than the previous value so we would pop the previous value it's not bigger than the next one so we leave it as is now suppose instead of that we put a three here well in that case we're going to pop this and we're going to pop this so this is why a stack is useful because we only need to look at the end of it this allows us to make it pretty efficient like each operation is going to be a constant time and as long as we're smart enough to make sure our stack is always monotonically decreasing or obviously like values can be equal as well if they're adjacent then we can solve this problem really really efficiently with a stack and basically ignore the fact that this is a link list problem until the end and at the end of the problem we will take our stack and convert it back into a linked list I'm going to quickly just walk through like in 30 to 60 seconds how that would work on this example problem and then we're going to code it up and then we're going to look at a slightly more optimized solution so suppose this is our stack we go through the linked list we just have like a current pointer or something and we just iterate over this length list we look at five that's great just go ahead and add five next value two so at this point we look at the two we want to add this to the stack should we pop the previous value no it's fine because these are monotonically decreasing we can put five and two there now we get to 13 though before we can push the 13 we want to make sure that this stack stays monotonically decreasing because as long as we guarantee that we're kind of solving this problem we will be able to filter out the values that have a greater value after them so basically 13 is greater than two so let's pop the two it's also greater than five so pop the five and then after that we can add the 13 here next we'd see three three is not greater than 13 so this is fine so far then we look at eight8 is greater than three so let's go ahead and remove that but it's not greater than 13 so leave it as is and then so this is the result of the problem and so the only thing we do at this point is just iterate over the stack and convert it into a length list which is pretty trivial I think so I'll just show that in the code okay so now moving on to the code I'm going to create that stack I was talking about and then we're going to have like a current pointer starting at the beginning of the link list and and while the current pointer is non-null let's iterate over the length list now ultimately what we want to do is for the stack we want to append the current value to the stack and then we want to shift the pointer to the next node so this is very straightforward but all this is doing is converting it into a list we want to make it monotonically decreasing so let's add a condition before all of this while the stack is not empty and the current value of the node that we're at is greater than the previous value on the stack which in Python you can get with -1 as the index while this is true then we will pop from the stack we don't really care about the value that we popped this is just the node that we are going to remove from the linked list and then after all of this let's convert it into a linked list so for this reason I'm going to have a dummy pointer and I'll kind of briefly explain why in case you're new to dummy pointers I always get questions about this so let me first show you what I'm going to do I'm going to have just a dummy node and I'm going to set current equal to the dummy and then I'm going to go through every value in the stack and of course we want to convert this value back into a node and then we want to add it to the end of our linked list which we can get with current so we're going to say current. nextt is where this new node is going to be inserted and let's also not forget to move current to the next pointer and then what I'm going to return is dummy. next because this is going to be the head of the length list now why did I do it this way the alternative would have been something like this having head and let's call it new head or something the new head of like the result that we're going to return and if we do it this way you'll notice when you first start out you have to set this equal to null so now when I am inserting this new node to the end of the linked list I have to add an if statement to check right now is the head null because if it is then we would just Set current or we would set that new node into this position but if it's not null then we would do this what I have here current. next is equal to the new node So to avoid that if statement we're just using a dummy pointer I know it doesn't save a ton of code but I think it makes the solution more simple and so this is the whole code I'll run it to make sure that it works whoops I had a very trivial typo this should be to the next pointer I'm pretty sure when I was talking about I said it correctly but typed it out wrong unfortunately as you can see the code does work so this is a linear time solution as you can kind of tell we're going through the linked list once and then possibly a second time for the remaining values but the space complexity is also Big O of n from the stack that we are using so big O of n time and space we can get this down to Big O of one space and big of n time let me show you how we can do that the idea is actually Rel relatively simple suppose this is our length list and just to exaggerate this and to make it really obvious let's instead of this problem let's assume we're given some Global number let's say it's 10 and it may or may not exist in the link list but we want to remove every node that has a value less than 10 and so we do that and it's pretty easy to do that we just iterate over the link list and for every value just compare it to 10 that's obviously linear time and constant space the one issue we have is that this is not the same for every single node we will be looking at a different set of values like for this node we want to know if any of these is greater than five and for this node we want to know if any of these are greater than two and etc etc it's just going to keep kind of going like this right how can we know if there's any values greater than five unless of course we've gone through this entire portion how can we possibly know that and how can we know if there's any values greater than two unless we've gone through this portion but if you see the order that we're going in if we solve this left to right we'll first have to scan through this part then scan through this part then this part etc etc now imagine if we were actually going from right to left what would the problem look like well for eight we would ask ourselves is there any value to the right of eight that is greater than eight well there's nothing to the right of it so this is fine right now what about three we want to know is there any value to the right of three that's greater than it and yes there is there's eight so I guess we can skip this and so now we get to 13 we ask the same question but how should we answer the question should we go back and scan through this to ask ourselves if there's a value greater than 13 or can we do something a little bit smarter and just maintain what the current Max is if we're iterating from left to right notice to answer this question we have to go through this to answer this question we have to go through this wouldn't it be better if we solved this sub problem then this one then this one and then finally the whole thing I think so that's how we're going to solve the problem but the main question at this point would be to answer how are we going to iterate in reverse order cuz we can't really do that the best way would be constant Space by just like duplicating this into an array or something like that well if we're allowed to change the pointers and sometimes it's not allowed so it's always worth clarifying with your inter viewer but if we are allowed to modify the pointers we can just reverse every single pointer in this linked list and then we can accomplish what we wanted to we can then filter out the nodes in linear time and constant space and then once we're done with that before we return the linked list let's make sure to undo the reverse thing that we kind of did so undo all of these reversals so this is a linear time solution and constant space let's code it up since we are going to need to do the reverse couple times it's definitely worth creating a helper method for that so this is I think its own leak code problem so this is like one of the easy leak code problems you can probably look it up if you want but I'll kind of gloss over this part we're basically reversing a link list so we're just reversing the pointers I'm going to have two pointers maintaining the previous node which let's say is just going to be null and the current node which is going to be the head and then while the current node is nonnull we are going to set current. next equal to the previous we're just reversing the pointer then we're going to set previous and current to updated we're going to shift them to the right previous is going to be set to current current is going to be set to current. nextt but how can we do that if we just changed it this is why we create a temporary variable so that's what I'm going to do here and then instead of assigning this to current. next which we change over here let's assign it to Temp once this is done we want to return the head of the linked list like after it's been reversed that is probably going to be where previous leaves off current is going to be null by the time this Loop ends previous should be pointing at the head so return previous now just two things that we want to do we want to First reverse the input that we're given so we're going to sign head to the reversal of it and then eventually we're going to return this link list as well after we reverse it again so let's do this now before we can obviously do this we do have to filter out those values we have to remove those nodes how can we do that nothing super crazy let's have a pointer current and set it to the head of the linked list and let's maintain the current Max which is let's say initially the current value that we're at so while this is I guess the like subtle part I'm going to say while not current but current. next because first of all with current we're starting at the end of the length list and we know that we're definitely never going to remove that node there's no values to the right of that node so we can't remove it there's not going to be any greater values so we are currently at Kerr cerr is not the candidate to be removed current. next is the candidate to be removed while current. nextt is not null we want to know is current. nextext do value less than the current Max that we have seen so far or is it not now if it is if this is the one that we want to remove current. then let's just skip that node so in terms of pointers we can say current and set the next pointer to be current. next. next so we're just skipping a node and this is why we check for current. next but we still maintain a pointer to the current node because to remove current. next we need a pointer to the previous node so that we can update the pointer of that prev node this is where we removed that node that's great in that case the current pointer doesn't really change because current. nextt is still changing in the other case things are going to change we're going to shift our pointer current is going to be current. next and before that we're also going to update our current Max actually because if this is equal to that or greater than it then we might as well down here say current. Max is equal to the current value or rather the current. next uh. value cuz that is what we are comparing at with this is the entire code let's run it to make sure that it works as you can see it does it's pretty efficient and it's definitely more memory efficient than the previous solution if you're preparing for coding interviews check out NE code. thanks for watching and I'll see you soon