Dummy node is actually not required if we run the loops till 'while right.next'. The reason we are using a dummy node is to handle the special case when we have to remove the first (head) node in a list of length 2
Also, usage of 'while right.next' requires dealing with additional edge case when the list is empty, i.e. head=None. Not critical, but more elegant with dummy node
@@evgeniyazarov4230 Not really more elegant with dummy node. It sounds unnecessary and surplus to needs, actually @DHAiRYA2801 's solution makes more sense.
@@chrischika7026 Hey, I hope you didn't think I was trying to be mean when I made that comment. I was just curious, not in a malicious way. And yes, I have received one. I hope you get one too or already have. Nice to see someone standing up for others, but I didn't mean it that way.
Can be done in one while loop also: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: dummy = ListNode(0, head) first = dummy second = head while second: if n > 0: second = second.next n -= 1 else: second = second.next first = first.next first.next = first.next.next return head
Finding nth mode from the end of a linkedlist, can reverse the list and get a pointer, or can use two pointers, the space between them is n and move them forward at the same speed. When one reaches the end, the other will be at the nth element from the end
Managed to do this without looking at the solution, and thought mine was way more simple. Got 97.5% at 30ms. Basically count up the length of the linked list. Then use a while loop to keep track of the prev, current, and next nodes and drop the length by 1 until n is reached. Then set the prev.next to the current.next. Have to handle a few edge cases, but should just be O(n+n) -> O(n). Might be useful. Thanks for the videos! class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: length = 0 current = head prev = None # from end of list while current: length += 1 current = current.next current = head count = length while count >= n: if count == n: if prev: prev.next = current.next elif n == 1: head = None else: head = current.next else: prev = current current = current.next count -= 1 return head
@@ProfessorQuality while your solution may simplify to O(n), the interviewer will likely follow up by asking for a single pass solution. good to know this as an optimal solution
@@jrumac The solution that neetcode provides is not single pass solution. He first moves the right pointer to the nth position, which in worst case could be O(n) and then moves the left pointer just before the nth postion which in the worst case could be O(n-1), which makes is O(2n) -> O(n). Same as @PorfessorQuality's solution
Here's how I did it, hopefully this helps people understand this problem in a different way. It's different from the way shown in the video in that it is kind of a 2 pass solution where we first count the amount of nodes in the linked list and then do some simple math to figure out the amount of times we need to traverse the linked list on the second pass. Ultimately, your pointers end up on the node that is going to be "deleted" and on the node before it. This solution should boil down to O(N) time, but correct me if I'm wrong. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: # assign dummy node before head node dummy = ListNode(0,head) # count nodes in LL lengthOfLL = 0 counterNode = head while counterNode != None: lengthOfLL += 1 counterNode = counterNode.next # calculate amount of times needed to traverse nodes moveTimes = lengthOfLL - n # assign node to delete and node behind deleteNode = head followNode = dummy # traverse linkedlist with the amount of times needed to move, decrement moveTimes while moveTimes > 0: deleteNode = deleteNode.next followNode = followNode.next moveTimes -= 1 # deleteNode pointer is now at the node that needs to be "deleted" # all we need to do now is set the node before it (followNode in this case) to the -.next # of the current node we are at (deleteNode) followNode.next = deleteNode.next # basically return the head node. return dummy.next
@@wingforce8530 Sorry for replying to an old comment. The time complexity remains same for both the solution. But, if you check the follow up it asks you to do it in one pass.
I had a question, so instead of using dummy node can't we just put the condition where right node stops as soon as it reaches "right->next=NULL" in this way we can simply do left->next=y after that left->next=y->next, delete/free(y) ??
instead if asked n = 2, we can use n = 3 and solve, by doing so we would be behind by one node on left, we should handle edge cases for this approach, it would be when n = 1 and length = 1, then we should take care to return head.next
@@abrarulhaqshaik This is possible public ListNode removeNthFromEnd(ListNode head, int n) { if(head.next == null){ return null; } ListNode temp = head; for(int i = 0; i < n; i++){ temp = temp.next; }
if(temp == null){ head = head.next; return head; }
ListNode pre = head;
while(temp.next != null){ pre = pre.next; temp = temp.next; }
Why do we need to create a dummy node? Can't we just return the head instead? When we return dummy.next, we essentially just return the head if I am not mistaken.
Try returning head on the given example case `linked_list = [1]` and `n = 1`. You'll see that you need a dummy node to delete a node in a linked_list of length 1.
Thank you very much for your clear explanation. I really love NeetCode. One feedback: Instead of playing the youtube video on a popup, I think you can open UA-cam video directly when the "camera" button is clicked. It would be easier for me and other people to like the videos :D
I think it's time complexity O(n^2) because you could be removing the last node, iterating twice through the linked list. Once to get the length and once to remove it.
thank you finally got it.... my thought process was like,,, if i need to remove the n-th node from end, i need to find, how far it is from start, then traverse from start to reach that node.. ahaha
@@dumdum407 Still twice as much work. It's one of those things that would be a drag on performance but rarely noticed because it won't blow up in production by being n^2.
With 2 extra nodes only public ListNode removeNthFromEnd(ListNode head, int n) { if(head.next == null){ return null; } ListNode temp = head; for(int i = 0; i < n; i++){ temp = temp.next; }
if(temp == null){ head = head.next; return head; }
ListNode pre = head;
while(temp.next != null){ pre = pre.next; temp = temp.next; }
Hey master, nice approach. However, this is still avg of O(nodes) + O(nodes - n) with the two pointers which is mostly the same as passing twice once you find the tail and know the number of nodes. Yes, it's O(n) but just for definition but that was not what they asked. Since they did not mention any memory constraint, a way to do this in exactly O(nodes) is to have a queue with a max of N + 1 nodes so that every time we go next, we popleft O(1) and append O(1). By the time we hit the Tail, we can just do the last nMinusOne = popLeft(), nMinusOne.next = nMinusOne.next.next. WDYT?
I think an easier way to do this is too find the position of N and delete it. One way to do this is too take the length of the llist and subtract N from it. This will give us the position. We iterate through again and once our current position is less than the target position ( len_llist - N), that we can connect the links accordingly. I don't know how much this makes sense writing it, but here is the solution I came up with: class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: ll_len = 0 curr = head while curr: ll_len += 1 curr = curr.next
prev = None curr_pos = 0 target = ll_len - n # reset curr curr = head if ll_len == n: head = curr.next while curr and curr_pos < target: prev = curr curr = curr.next curr_pos += 1
I failed to solve previous problem (Reorder List). Learning the slow and fast pointer technique helped me to solve this one. It seemed like I need to use something similar. Right pointer ahead just tells us when the left is at appropriate node.
Nice! Sir, I just love the way you explain the answers. I think we can also stop the iteration when R.next == nil so our L will be at position where we wanted. Then we won't need dummy node.
I wonder if we can do it without using an additional node. but with a tmp node keeping track of previous slow node. Leetcode has too many edge cases, hard to resolve.
Can you please explain me that line left.next = left.next.next. Is it not going to fail when n is not 2? left.next.next is only going two nodes ahead. What if n was 3 ? Wouldnt it be then left.next.next.next?
Nice, also you do not need to check if right is not null in the while loop 'while n > 0 and right:'. By definition if we start from head we know that the length is at least n so shifting by N is always possible.
you can also solve it by checking the list length then que the position where is going to be removed and the iterate until the position before removed then we could move the next pointer to that pointer to be next.next that way the node is removed from the list like this: function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null { let listSize = 0; let curr = head; while (curr) { listSize++; curr = curr.next; } if (n > listSize) { return head; } let dummy = new ListNode(head?.val) dummy.next = head let position = listSize - n; curr = dummy; for (let i = 0; i < position; i++) { curr = curr?.next; } curr.next = curr.next.next; return dummy.next }
I stored all the nodes in a list, and then just did a[-n - 1].next = a[-n].next, considering 'a' to be the list in which all the nodes were stored. This method takes only 1 pass, at the cost of n space.
why have a dummy pointer when we can have left start at the first node, right start at (first + n)th node and run a loop until right.next == Null instead of right == Null?
This can run into problem in the edge case when n = # Nodes. Consider e.g. head=[1] and n=1. In that case using right.next==Null would return an error, because right itself would become Null after the first while loop in the code (where right is offset from left by n nodes). Using a dummy pointer will avoid this problem
C++ approach: class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new ListNode(); dummy -> next = head; ListNode* left = dummy; ListNode* right = head; while(n>0 && right){ right = right -> next; n--; } while(right){
left = left -> next; right = right -> next; } //delete left -> next = left -> next -> next; return dummy->next;
Here's what I did, completely different from the video but still is O(n) time complexity: # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: length = 0 current = head while current: length+= 1 current=current.next if n == length: return head.next current = head for _ in range(length - n - 1): current = current.next current.next = current.next.next return head I just calculated the length of the list and went to the length - n -1th element and disconnected it from the node. Lmk what you guys think!
You solution works. But, have you checked the follow up? The follow up says, "can you do it in one pass?" If you have to do it in one pass, you have to take this approach.
Is there any time complexity difference between going through an array once with 2 pointers vs going through an array twice with 1 pointer? I solved this question by getting the length first and then iterating until length - n but I'm not sure if it's technically slower
Technically slower since your time scales 2x as much w/ size of the input, but still O(n) time complexity Your approach is O(2n) which reduces -> O(n) since we don't care about coefficients for TC
@@yskida5 Both approaches are O(2n) . In fast and slow pointer approach, we are running 2 operations in one pass - one for fast and one for slow. In @3030's approach, we use 2 passes but use only one pointer to iterate. So both are equally efficient. I could be wrong but this is how I see it.
@@nitinullas you are wrong, this is not how time complexity works. In this video it's O(n) because we only have 1 loop of length n, the 2 operations you are talking about are both O(1) so it doesn't make it O(2n)
@@chrischika7026 Taken directly from the Big O Notation wikipedia article: "Multiplication by a constant Let k be a nonzero constant. Then O(|k|⋅g) = O(g)." So no I am not wrong and it is completly okay and even standard to remove all constant.
Instead of dummy node you can also use another pointer following left pointer so when our left pointer is at nth node our following pointer is at the previous of nth node.
hmm, is there a reason no one is using a queue to hold the nth previous nodes? other then having to worry about a cyclic list, it seems it'd be faster perhaps.
@@Unknownn716 Yes from queue import x : if I want to be quick about it Somehow on leetcode, any solution that I use something from the queue collection has a super slow runtime. I get much faster runtimes if I implement my own queue with a linked list. You'd think using the LifoQueue would be faster then using a normal list since when the list size grows it has to be moved but I don't know. You can have the same code submitted to beating 99% and then if you re run it a minute later its only beating 3%. I can't make heads or tails :D
I understand the problem and I thought of the same thing. My problem was that I returned head instead of dummy.next cz it works for all the cases except one.
I did the same. I understand why it is so. Input: [1] 1 Output: [1] Expected: [] After removing the only node 1, the dummy(left) points to the null(right). If we return head, it returns 1, but 1 is not in our linked list anymore.
I did the same except I accounted for it with a condition i.e if left==dummy in the end that means the node to be deleted would be the head node therefore I return head.next in that case, hence it passed! if left==dummy: return head.next else: return head
Thank you for the great explanation. Quick question. Could we set the distance between the two pointers to n+1 (3)? This solution would not require a dummy node.
@@PIYUSH-lz1zq The question says that there can be at minimum 1 node, so there could be an if statement to handle the edge case for 1 node. 2 or 3 nodes can be handled by Kea's suggestion.
dont we have to remove the pointer of the desired node to remove from that node to the next one? for example say we have 1->2->3->4 and we want to remove 3. if thats the case, then we must have 2 point to 4. 1->2->4. However, wouldnt 3 be pointing to 4 still since we did not change that pointer?
Why is it when I keep a seperation of n nodes from the left to the right pointer I am guaranteed the left pointer will land on the node to be deleted when right pointer goes null?
Great explanation! Instead of using a dummy we can just store prev of left and if left is None we can `return left.next` else we can `prev.next = prev.next.next`
If n > length, should this just return the list unmodified (the original head)? In the solution, if right reaches the end in the first while loop, then left will never be updated, and left.next = left.next.next will whack off the head. After the first while loop, I added if n > 0: return head
No one is talking about how weird the algorithm is, I mean it works but I still can't understand the reason why right going out of the list will have left landed at the node that we want to delete
i think we should properly remove the node to be removed by making its next pointer to none like this left.next.next, left.next = None, left.next.next this is without using a temp variable
if there's only one node in the linkedlist for example : [2], and we are deleting the 1st from the tail. The end result should be [].(empty linked list), since we need to remove head from the list. In this case, we need to return dummy.next to ensure the correct result.
Cant we find the size of the list which is O(n) and and do size-n this is also going to take us to the node which we want to delete..so the overall time complexity will be O(n+n) = O(n).
Good video. I did easier. But I have checked hints at first to understand how to solve. I set before_delete = None, delete_node = head end_node = head When end_node reaches None. Delete node is exactly what we need to delete. Last steps: before_delete.next = delete_node.next delete_node = None But if you have [1] one element in list or you have 2 and need to delete second which means first one from the beginning of the list you need to take extra steps. Can show how if it is needed. My works faster a bit because no need to create a dummy node and less space also.
This seems awfully complicated and using pointers for the sake of it. Why not just get the length of the linked list, then loop through it. When you arrive at the node you need to delete, just ignore that node and add the rest of the list to dummy and return
Really love ur content but ur code won't work for list: [3] and 1 i.e it won't work if the nth value is same as that of the length of the list .. It's not capable of deleting head node....
Linked List Playlist: ua-cam.com/video/G0_I-ZF0S38/v-deo.html
Why not just make the space between the left and right pointers n+1 instead of n? Then you wont need to create this dummy node
can you please show the solution by reverseing * which you were talking in starting please please
please include cpp and java solution also in every video
it will be helpful
Hands down the best explanation I've seen...and it's in Python!
Dummy node is actually not required if we run the loops till 'while right.next'. The reason we are using a dummy node is to handle the special case when we have to remove the first (head) node in a list of length 2
Also, usage of 'while right.next' requires dealing with additional edge case when the list is empty, i.e. head=None. Not critical, but more elegant with dummy node
I was thinking if we change the condition of while to n=0 we won't need the dummy because then L will be n+1 steps behind R
needs to be upvoted. not completely clear from the video.
@@evgeniyazarov4230 Not really more elegant with dummy node. It sounds unnecessary and surplus to needs, actually @DHAiRYA2801 's solution makes more sense.
# l, r pointer get n space
l, r= head, head
for _ in range(n):
r = r.next
# when case is delete the first node
if not r:
return head.next
# l move to preTarget
while r.next:
l = l.next
r = r.next
l.next = l.next.next
return head
To the point, concise, not bullshit. Your video deserves more rewards!
You'll be the reason I get my first SWE Internship
did u end up getting one :)
@@gabbyamedu1485 considering it was 3 years ago, I hope so
@@gabbyamedu1485I’ll get one, you can ask me, I’ll reply when i do
have you
@@chrischika7026 Hey, I hope you didn't think I was trying to be mean when I made that comment. I was just curious, not in a malicious way. And yes, I have received one. I hope you get one too or already have. Nice to see someone standing up for others, but I didn't mean it that way.
Upvoted it the moment you finished explaining and started coding..........Hats OFF........It's still fresh as in 2022
Two pointers is really a life-saver. Once understood, it almost solves any tricky part of the problem
Can be done in one while loop also:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
first = dummy
second = head
while second:
if n > 0:
second = second.next
n -= 1
else:
second = second.next
first = first.next
first.next = first.next.next
return head
Finding nth mode from the end of a linkedlist, can reverse the list and get a pointer, or can use two pointers, the space between them is n and move them forward at the same speed. When one reaches the end, the other will be at the nth element from the end
The follow-up is that it should be done is one pass.
Great channel for programmers this channel has great potential....
Thanks a ton!!💖 Since the condition is that '1
Loved how the Dummy head node technique removes the need to handle several edge cases, like when the nth node is the original head.
Managed to do this without looking at the solution, and thought mine was way more simple. Got 97.5% at 30ms.
Basically count up the length of the linked list. Then use a while loop to keep track of the prev, current, and next nodes and drop the length by 1 until n is reached. Then set the prev.next to the current.next. Have to handle a few edge cases, but should just be O(n+n) -> O(n). Might be useful. Thanks for the videos!
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
length = 0
current = head
prev = None
# from end of list
while current:
length += 1
current = current.next
current = head
count = length
while count >= n:
if count == n:
if prev:
prev.next = current.next
elif n == 1:
head = None
else:
head = current.next
else:
prev = current
current = current.next
count -= 1
return head
this will be slower by complexity. The leetcode time doesnt matter.
@@alihassanamin7854 It could be slower (it isn't), but it wouldn't be due to complexity as O(2n) -> O(n) gives same time complexity.
@@ProfessorQuality while your solution may simplify to O(n), the interviewer will likely follow up by asking for a single pass solution. good to know this as an optimal solution
@@jrumac The solution that neetcode provides is not single pass solution. He first moves the right pointer to the nth position, which in worst case could be O(n) and then moves the left pointer just before the nth postion which in the worst case could be O(n-1), which makes is O(2n) -> O(n). Same as @PorfessorQuality's solution
Here's how I did it, hopefully this helps people understand this problem in a different way. It's different from the way shown in the video in that it is kind of a 2 pass solution where we first count the amount of nodes in the linked list and then do some simple math to figure out the amount of times we need to traverse the linked list on the second pass. Ultimately, your pointers end up on the node that is going to be "deleted" and on the node before it. This solution should boil down to O(N) time, but correct me if I'm wrong.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
# assign dummy node before head node
dummy = ListNode(0,head)
# count nodes in LL
lengthOfLL = 0
counterNode = head
while counterNode != None:
lengthOfLL += 1
counterNode = counterNode.next
# calculate amount of times needed to traverse nodes
moveTimes = lengthOfLL - n
# assign node to delete and node behind
deleteNode = head
followNode = dummy
# traverse linkedlist with the amount of times needed to move, decrement moveTimes
while moveTimes > 0:
deleteNode = deleteNode.next
followNode = followNode.next
moveTimes -= 1
# deleteNode pointer is now at the node that needs to be "deleted"
# all we need to do now is set the node before it (followNode in this case) to the -.next
# of the current node we are at (deleteNode)
followNode.next = deleteNode.next
# basically return the head node.
return dummy.next
you are rigth but it's less optimized than the neecode solution.
This was my approach as well, nice
@@Rajmanov they are Nx2 vs. N + N, no difference at all
@@wingforce8530 Sorry for replying to an old comment. The time complexity remains same for both the solution. But, if you check the follow up it asks you to do it in one pass.
I had a question, so instead of using dummy node can't we just put the condition where right node stops as soon as it reaches "right->next=NULL" in this way we can simply do left->next=y after that left->next=y->next, delete/free(y) ??
I thought about and tried that too. I guess no because the when there's only one node, the head will be removed as well
instead if asked n = 2, we can use n = 3 and solve, by doing so we would be behind by one node on left, we should handle edge cases for this approach, it would be when n = 1 and length = 1, then we should take care to return head.next
@@abrarulhaqshaik I tried this but I don't think it works because if the list size is 2, then None.next will cause an error.
@@jakenguyen2584 that is what I meant edge cases, handle that, and get done. It worked thats why I commented 💀
@@abrarulhaqshaik This is possible
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head.next == null){
return null;
}
ListNode temp = head;
for(int i = 0; i < n; i++){
temp = temp.next;
}
if(temp == null){
head = head.next;
return head;
}
ListNode pre = head;
while(temp.next != null){
pre = pre.next;
temp = temp.next;
}
pre.next = pre.next.next;
return head;
}
Why do we need to create a dummy node? Can't we just return the head instead? When we return dummy.next, we essentially just return the head if I am not mistaken.
Try returning head on the given example case `linked_list = [1]` and `n = 1`.
You'll see that you need a dummy node to delete a node in a linked_list of length 1.
Thank you very much for your clear explanation. I really love NeetCode.
One feedback: Instead of playing the youtube video on a popup, I think you can open UA-cam video directly when the "camera" button is clicked.
It would be easier for me and other people to like the videos :D
I literally smiled after learning about the trick here! Amazing!!!
One word for you, the ultimate Leetcode boss I have ever seen
why not itterate over the the linked list once to get the length and then remove length - nth node? still time complexity O(N)?
the question asks you to do it in single pass
I think it's time complexity O(n^2) because you could be removing the last node, iterating twice through the linked list. Once to get the length and once to remove it.
@@andreiflorea39 Iterating twice would mean O(n) + O(n), which is still O(n)
@@kewlv2kyou’re right looking back idk what i was saying in that comment lol
yes, this is the more intuitive approach, but less efficient/clean
thank you finally got it.... my thought process was like,,, if i need to remove the n-th node from end, i need to find, how far it is from start, then traverse from start to reach that node.. ahaha
that's not a bad start tbh. Its still only 2 passes through the list, meaning O(2n) == O(n) ? or am I wrong on that.
@@dumdum407 Still twice as much work. It's one of those things that would be a drag on performance but rarely noticed because it won't blow up in production by being n^2.
U a God:
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
dummy = slow = ListNode(0,head)
fast = head
for _ in range(n):
fast = fast.next
while fast:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next
With 2 extra nodes only
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head.next == null){
return null;
}
ListNode temp = head;
for(int i = 0; i < n; i++){
temp = temp.next;
}
if(temp == null){
head = head.next;
return head;
}
ListNode pre = head;
while(temp.next != null){
pre = pre.next;
temp = temp.next;
}
pre.next = pre.next.next;
return head;
}
Hey master, nice approach. However, this is still avg of O(nodes) + O(nodes - n) with the two pointers which is mostly the same as passing twice once you find the tail and know the number of nodes. Yes, it's O(n) but just for definition but that was not what they asked. Since they did not mention any memory constraint, a way to do this in exactly O(nodes) is to have a queue with a max of N + 1 nodes so that every time we go next, we popleft O(1) and append O(1). By the time we hit the Tail, we can just do the last nMinusOne = popLeft(), nMinusOne.next = nMinusOne.next.next. WDYT?
I think an easier way to do this is too find the position of N and delete it. One way to do this is too take the length of the llist and subtract N from it. This will give us the position. We iterate through again and once our current position is less than the target position ( len_llist - N), that we can connect the links accordingly. I don't know how much this makes sense writing it, but here is the solution I came up with:
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
ll_len = 0
curr = head
while curr:
ll_len += 1
curr = curr.next
prev = None
curr_pos = 0
target = ll_len - n
# reset curr
curr = head
if ll_len == n:
head = curr.next
while curr and curr_pos < target:
prev = curr
curr = curr.next
curr_pos += 1
if prev:
prev.next = curr.next
return head
I failed to solve previous problem (Reorder List). Learning the slow and fast pointer technique helped me to solve this one. It seemed like I need to use something similar. Right pointer ahead just tells us when the left is at appropriate node.
Best explanation for this one I've seen, thanks
Nice! Sir, I just love the way you explain the answers.
I think we can also stop the iteration when R.next == nil so our L will be at position where we wanted.
Then we won't need dummy node.
I wonder if we can do it without using an additional node. but with a tmp node keeping track of previous slow node. Leetcode has too many edge cases, hard to resolve.
Also we can check on each step if R_pointer.next is null, and then, L_pointer.next is a node to delete
what do we need the dummy node for? why can't we just increase the difference between the left pointer and the right pointer by 1?
head=[1,2]
n=2
In that case would be a problem because we cannot increase difference more than n, there is no space for it.
Took me a second to understand why you did left.next.next but wow, that is insane.
Really good explanation, thank you
Can you please explain me that line left.next = left.next.next. Is it not going to fail when n is not 2? left.next.next is only going two nodes ahead. What if n was 3 ? Wouldnt it be then left.next.next.next?
@@DiptarajSen you need to remove 1 node. it's 2th node not 2 nodes.
Nice, also you do not need to check if right is not null in the while loop 'while n > 0 and right:'.
By definition if we start from head we know that the length is at least n so shifting by N is always possible.
you can also solve it by checking the list length then que the position where is going to be removed and the iterate until the position before removed then we could move the next pointer to that pointer to be next.next that way the node is removed from the list like this:
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
let listSize = 0;
let curr = head;
while (curr) {
listSize++;
curr = curr.next;
}
if (n > listSize) {
return head;
}
let dummy = new ListNode(head?.val)
dummy.next = head
let position = listSize - n;
curr = dummy;
for (let i = 0; i < position; i++) {
curr = curr?.next;
}
curr.next = curr.next.next;
return dummy.next
}
super clear explanation of this! thank you so much
I stored all the nodes in a list, and then just did a[-n - 1].next = a[-n].next, considering 'a' to be the list in which all the nodes were stored. This method takes only 1 pass, at the cost of n space.
bro that n space is ☠☠☠☠
why have a dummy pointer when we can have left start at the first node, right start at (first + n)th node and run a loop until right.next == Null instead of right == Null?
or have right node at (first+n+1)th node.
This can run into problem in the edge case when n = # Nodes. Consider e.g. head=[1] and n=1. In that case using right.next==Null would return an error, because right itself would become Null after the first while loop in the code (where right is offset from left by n nodes). Using a dummy pointer will avoid this problem
I hate python but every time that I see this type of videos, its not that bad , thnk u Neet
Thanks after your explanation, solution become easy understandable
C++ approach:
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode();
dummy -> next = head;
ListNode* left = dummy;
ListNode* right = head;
while(n>0 && right){
right = right -> next;
n--;
}
while(right){
left = left -> next;
right = right -> next;
}
//delete
left -> next = left -> next -> next;
return dummy->next;
}
};
Here's what I did, completely different from the video but still is O(n) time complexity:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
length = 0
current = head
while current:
length+= 1
current=current.next
if n == length:
return head.next
current = head
for _ in range(length - n - 1):
current = current.next
current.next = current.next.next
return head
I just calculated the length of the list and went to the length - n -1th element and disconnected it from the node. Lmk what you guys think!
You solution works. But, have you checked the follow up? The follow up says, "can you do it in one pass?" If you have to do it in one pass, you have to take this approach.
@@racecarjonny8460 Hmm yes. I did implement this later on.
Is there any time complexity difference between going through an array once with 2 pointers vs going through an array twice with 1 pointer? I solved this question by getting the length first and then iterating until length - n but I'm not sure if it's technically slower
Technically slower since your time scales 2x as much w/ size of the input, but still O(n) time complexity
Your approach is O(2n) which reduces -> O(n) since we don't care about coefficients for TC
@@yskida5 Both approaches are O(2n) . In fast and slow pointer approach, we are running 2 operations in one pass - one for fast and one for slow.
In @3030's approach, we use 2 passes but use only one pointer to iterate.
So both are equally efficient.
I could be wrong but this is how I see it.
@@nitinullas you are wrong, this is not how time complexity works. In this video it's O(n) because we only have 1 loop of length n, the 2 operations you are talking about are both O(1) so it doesn't make it O(2n)
@@guimauve522 WRONG. it is O(2n). look (O(1) + O(1)) == O(2) , then O(2) * O(n) == O(2n). you dont know how time complexity works
@@chrischika7026 Taken directly from the Big O Notation wikipedia article:
"Multiplication by a constant
Let k be a nonzero constant. Then O(|k|⋅g) = O(g)."
So no I am not wrong and it is completly okay and even standard to remove all constant.
Instead of dummy node you can also use another pointer following left pointer so when our left pointer is at nth node our following pointer is at the previous of nth node.
In this approach, there'll be an edge case when nth node from the end is also first node.
Can't we stop right pointer when the next to it is None (instead of right pointer itself is None)? This way we don't need dummy node
Wow, I finally understand this. Thanks!
really great explanation, better than other's ive seen
This is a beautiful explanation, thank you
wow thank you for your clear explanation!! love it!
Hats off to you my guy... The best explanation I've watched so far. You gained a new subscriber!
hmm, is there a reason no one is using a queue to hold the nth previous nodes?
other then having to worry about a cyclic list, it seems it'd be faster perhaps.
Hi, how did you use queue, are use it by : from queue import Queue ?
@@Unknownn716 Yes from queue import x : if I want to be quick about it
Somehow on leetcode, any solution that I use something from the queue collection has a super slow runtime. I get much faster runtimes if I implement my own queue with a linked list.
You'd think using the LifoQueue would be faster then using a normal list since when the list size grows it has to be moved but I don't know. You can have the same code submitted to beating 99% and then if you re run it a minute later its only beating 3%. I can't make heads or tails :D
That would be O(n) time and O(n) space
neetcode solution is O(n) time and O(1) space, and also addresses the followup one-pass requirement
Super clever logic, Thanks for your explanation !
best explanation. really clear and neat
I understand the problem and I thought of the same thing.
My problem was that I returned head instead of dummy.next cz it works for all the cases except one.
I did the same. I understand why it is so.
Input:
[1]
1
Output:
[1]
Expected:
[]
After removing the only node 1, the dummy(left) points to the null(right). If we return head, it returns 1, but 1 is not in our linked list anymore.
I did the same except I accounted for it with a condition i.e if left==dummy in the end that means the node to be deleted would be the head node therefore I return head.next in that case, hence it passed!
if left==dummy:
return head.next
else:
return head
wow. still don't understant how people came to this kind of solution. i used array to solve this problem.
Thank you for the great explanation. Quick question. Could we set the distance between the two pointers to n+1 (3)? This solution would not require a dummy node.
Bro, what if there are null or 1 or 2 or 3 node only then ??
dummy node helps for when question wants you to remove the first (head) node
@@axaxaxaxaxaxax33 thanks had the same question
@@PIYUSH-lz1zq The question says that there can be at minimum 1 node, so there could be an if statement to handle the edge case for 1 node.
2 or 3 nodes can be handled by Kea's suggestion.
yes it can work but little complex so dummy will be good because it also include all cases
dont we have to remove the pointer of the desired node to remove from that node to the next one? for example say we have 1->2->3->4 and we want to remove 3. if thats the case, then we must have 2 point to 4. 1->2->4. However, wouldnt 3 be pointing to 4 still since we did not change that pointer?
but, what's the different from count the list size = N first then count it again for N - n? for both the solution , the time complexity are O(N)
Why don't we count with one pass and reach the predecessor of correct node (count - n -1) in next pass? Really simple solution and still O(n).
youll have to handle multiple edge cases. what if the (len == n), implying (count - n - 1) is -1
another approach would be to use recursion, where you start count when you react to last node and delete the node once n and count matches
@@gavinsweeney1554 i don't think it's double pass. It's basically a sliding window, so O(n) time.
This is nice, with no further thought I have subscribed.
Clear explanation !👍
Why is it when I keep a seperation of n nodes from the left to the right pointer I am guaranteed the left pointer will land on the node to be deleted when right pointer goes null?
`while n > 0 and right` - I think you can just use `while n > 0`
Thanks a lot! This is really helpful.
Amazing explanation !! Thank you!
Great explanation! Instead of using a dummy we can just store prev of left and if left is None we can `return left.next` else we can `prev.next = prev.next.next`
If n > length, should this just return the list unmodified (the original head)? In the solution, if right reaches the end in the first while loop, then left will never be updated, and left.next = left.next.next will whack off the head. After the first while loop, I added if n > 0: return head
Read the problem constraints:
The number of nodes in the list is sz.
1
in [1,2] case, when fast points to 2, why the program tells me that fast is null?
is the 'and right' in the while loop condition necessary?
I was wondering if the n -= 1 is necessary.
Insted of checking for r=null can’t we check for r->next =null then we don’t need dummy node?
You are simply great man thanks for this.
thank you sir and am learning and getting better
Glad to be helpful! Best of luck
Nice job man, keep up!
No one is talking about how weird the algorithm is, I mean it works but I still can't understand the reason why right going out of the list will have left landed at the node that we want to delete
because we shift right by n? n is the n'th node from the end of the list we want to remove
I love you man! ❤ Keep up the great work
i think we should properly remove the node to be removed by making its next pointer to none like this
left.next.next, left.next = None, left.next.next
this is without using a temp variable
Very good explanation
Two pointers approach is still 2 pass solution, but we are doing these passes simultaneously)
Nice explanation and Thanks!
Thanks for great explaining
Can you tell me how the dummy Listnode is getting updated with latest left value, since it has not been explicitly updated
or how head is getting updated
What if we were to parse the entire list into an array, then take the n from last? It does have more memory complexity but it is still O(n) for time.
Can use a for loop to set the right pointer
Nonetype object has no attribute next
Left=left.next
whats the difference between dummy.next and head in the return statement? As in why won't it work if you return head
if there's only one node in the linkedlist for example : [2], and we are deleting the 1st from the tail. The end result should be [].(empty linked list), since we need to remove head from the list. In this case, we need to return dummy.next to ensure the correct result.
@@wenqianguo960 ahhh makes sense thank you!
@@hafiansari5881 no problem! :))
Cant we find the size of the list which is O(n) and and do size-n this is also going to take us to the node which we want to delete..so the overall time complexity will be O(n+n) = O(n).
why not do R->next ! = NULL so there would be no need to create a dummy node and we could start with the head.
Do n-1 start from head both right n left pointer
I did it in one pass using a hash map, but I guess the space complexity was O(n)
Good video. I did easier. But I have checked hints at first to understand how to solve.
I set before_delete = None,
delete_node = head
end_node = head
When end_node reaches None. Delete node is exactly what we need to delete.
Last steps:
before_delete.next = delete_node.next
delete_node = None
But if you have [1] one element in list or you have 2 and need to delete second which means first one from the beginning of the list you need to take extra steps. Can show how if it is needed.
My works faster a bit because no need to create a dummy node and less space also.
very clever, how do you come up with such ideas?
Is this solution considered one-pass? I mean, in the worst case scenario (n = 1) L and R are going through the whole array individually.
Why not we change value of nth node from last to its next node value and point to none?
I did this less efficiently. Reverse, delete nth node, reverse.
Hello, I am new to coding, why can't I just use head.pop(len(head)-n)? It spits out the same answer. Thank you in advance for anyone that could help.
dummy = ListNode(0,head)
right = head
Does this Linked List has 2 heads?
How does the program know that the dummy ListNode is a placeholder?
No... he created DummyNode and attached before head...
DummyNode = new Node()
DummyNode= head
So list looks like
DummyNode {val: null, next:head}
This seems awfully complicated and using pointers for the sake of it. Why not just get the length of the linked list, then loop through it. When you arrive at the node you need to delete, just ignore that node and add the rest of the list to dummy and return
Really love ur content but ur code won't work for list: [3] and 1 i.e it won't work if the nth value is same as that of the length of the list ..
It's not capable of deleting head node....
So clear!!
I've listened to your voice for so many hours now, but what's your name :D
If you use two pointers, does it count as one pass ? :D