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.
# 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
@@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
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 RU-vid video directly when the "camera" button is clicked. It would be easier for me and other people to like the videos :D
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.
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
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
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.
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`
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.
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 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.
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.
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.
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
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
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 }
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
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?
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
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
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?
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.
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.
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.
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.
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
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 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?
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.
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; } };
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
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....
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
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.
you could just run the 2nd while loop till right.next instead of making a dummy node. Also, I am not sure if this covers the case of root node deletion
I believe that would return an error for left.next = left.next.next when there's only one element in the linked list, since left.next would be a none and there are no edges for a none.
