Done thanks Using 3 pointers, current, previous and next Use a dummy node as head so the logic can be straightforward (avoids handling edge case of deleting the head of the list) Initialize prev to the dummy node, curr to head of list and next to node after it Pitfall:- When you delete a node, move forward current and next pointers while keeping previous in place Remember that you have a dummy head node so when returning the new list head you give dummy.nxt
#Without using prev just cur (accepted) def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: dummy = cur = ListNode() dummy.next = head while cur.next: if cur.next.val == val: cur.next = cur.next.next else: cur = cur.next return dummy.next
Recursive solution def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: if head is None: return None next = self.removeElements(head.next, val) if head.val == val: head = next else: head.next = next return head
Awesome as always. Could you please create playlists for other data structures?. Personally, I find it very efficient to solve several problems related to one data structure and then switch to another. BTW, since you don't override curr variable you don't need to use nxt :) Thank you very much. I belive you will rock in subscribers very soon
You can use 1 pointer if you have a 2-layer while loop. The pointer and pointer.next effectively work like 2 pointers (you'll also need a '3rd' pointer to the new list's root). The 2nd-layer while loop handles consecutive target values by incrementing the next pointer until it gets to a non-target node. Then the pointer itself is incremented in the outer while loop. It's important to null-check first in this method, before checking for a target value. Your videos are a great resource btw!
In the name of Lord. It is all about reference type mechanism. Initially prev and dummy has the same ref so changing prev reflects on dummy. However, once prev is changed to cur (prev = cur) dummy and prev have the different ref. That's why first iteration changes prev and dummy, then prev takes cur and no more connected to dummy (if we consider the case where first element has to be deleted) I also was stuck first and needed to dig into. Peace on u! Stop genocide in Palestine!
for java people : class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummyhead = new ListNode(); // act as a previous node ListNode tail = dummyhead; dummyhead.next = head; ListNode temp = head;
we are not touching the dummy.next it is always pointing to the head of the linked list . dummy.next is going to change ONLY if continuous start positions got the value which we have to remove.
here is a solution with out creating a dummy node prev, cur = head, head while cur: if head.val == val: head = head.next prev, cur = head, head elif cur.val == val: prev.next = cur.next cur = prev.next else: prev = cur cur = cur.next return head your solution super useful, but I guess we don't need nxt dummy = ListNode(next=head) prev, cur = dummy, head while cur: if cur.val == val: prev.next = cur.next else: prev = cur cur = prev.next return dummy.next
there is a bug in this video while(cur) { ListNode* nxt = cur->next; if(cur->val == val) pre->next = nxt; else { pre->next = cur; >>> this step is ignored in this video (7:11) pre = cur; } cur = nxt; }
If the node you are removing is the head, why would you not just make the head the next element and then nothing changes except the previous head falls off the linked list?
because you will need to write extra two or three lines to update the head pointer each time if the elem to remove is head, it is more elegant and simpler to use the dummy node thing.
Is there something I'm missing in the explanation? This makes sense but when I try this solution I keep running into an attribute error where the list doesn't support the next attribute
This is confusing you say we use two pointers and it seems like the dummy is one of the pointers but then you talk about moving both pointers every time , well then how could dummy point to the head? Sorry i think you are not clear enough
by using the listnode class we are building duplicate linked list awith nor values and then we dynamicallu add the values of that node using the prev and the cur pointer as you can see that the values in the current node has the actual head value that we are comparing other than that we are just using prev to update the values
@@webknowledge9989 where is the head getting updated only prev and curr are getting updated and curr has copy of head if curr is getting updated than how it can update the head
@@mohitsharma38 it's important to understand that you are not creating copies at any point here. The variables are just references to the actual objects (i.e head). You are modifying the contents of the object whenever you edit the object's properties like next and val.
this is how you itterate through the linked list, on line 19 he sets curr to the next value and it will continue to the next value until it is NULL ie. at the end of the linked list and the while loop will end.
what do you think of this Python solution? I know it's O(n) time and space complexity but this was my first attempt :) nums = [ ] dummy = ListNode() current = dummy while head: nums.append(head.val) head = head.next for num in nums: if num != val: current.next = ListNode(num) current = current.next return dummy.next
Linked List Playlist: th-cam.com/video/G0_I-ZF0S38/w-d-xo.html
Done thanks
Using 3 pointers, current, previous and next
Use a dummy node as head so the logic can be straightforward (avoids handling edge case of deleting the head of the list)
Initialize prev to the dummy node, curr to head of list and next to node after it
Pitfall:-
When you delete a node, move forward current and next pointers while keeping previous in place
Remember that you have a dummy head node so when returning the new list head you give dummy.nxt
Damnn, that dummy node technique is very cool. It saves the hassle of updating the head pointer and dealing with 3 edge cases.
#Without using prev just cur (accepted)
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy = cur = ListNode()
dummy.next = head
while cur.next:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
Great Solution Bro
Love the consistent uploads, ty and keep up the good work!
Thanks, that means alot :~)
Recursive solution
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
if head is None:
return None
next = self.removeElements(head.next, val)
if head.val == val:
head = next
else:
head.next = next
return head
Awesome as always.
Could you please create playlists for other data structures?.
Personally, I find it very efficient to solve several problems related to one data structure and then switch to another.
BTW, since you don't override curr variable you don't need to use nxt :)
Thank you very much. I belive you will rock in subscribers very soon
You can use 1 pointer if you have a 2-layer while loop. The pointer and pointer.next effectively work like 2 pointers (you'll also need a '3rd' pointer to the new list's root). The 2nd-layer while loop handles consecutive target values by incrementing the next pointer until it gets to a non-target node. Then the pointer itself is incremented in the outer while loop. It's important to null-check first in this method, before checking for a target value. Your videos are a great resource btw!
Why does the prev.next = curr.nxt affect the values in dummy node? I assumed it wasn't going to affect the dummy node because it was just a copy.
In the name of Lord.
It is all about reference type mechanism. Initially prev and dummy has the same ref so changing prev reflects on dummy. However, once prev is changed to cur (prev = cur) dummy and prev have the different ref. That's why first iteration changes prev and dummy, then prev takes cur and no more connected to dummy (if we consider the case where first element has to be deleted) I also was stuck first and needed to dig into.
Peace on u!
Stop genocide in Palestine!
for java people :
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummyhead = new ListNode();
// act as a previous node
ListNode tail = dummyhead;
dummyhead.next = head;
ListNode temp = head;
while (temp!=null)
{
if (temp.val == val)
{
tail.next = temp.next;
}
else{
tail = temp;
}
temp = temp.next;
}
return dummyhead.next;
}
}
Nice explanation especially that dummy node one
You have no idea how much this video has helped me with my assignment!! Thank you so much!! xxxx
If there was 1 at the last position of the list, wouldn’t the dummy node now point to the last node(after removing 1)?
we are not touching the dummy.next it is always pointing to the head of the linked list . dummy.next is going to change ONLY if continuous start positions got the value which we have to remove.
Thanks, bro, it's helping me a lot, much appreciated
here is a solution with out creating a dummy node
prev, cur = head, head
while cur:
if head.val == val:
head = head.next
prev, cur = head, head
elif cur.val == val:
prev.next = cur.next
cur = prev.next
else:
prev = cur
cur = cur.next
return head
your solution super useful, but I guess we don't need nxt
dummy = ListNode(next=head)
prev, cur = dummy, head
while cur:
if cur.val == val:
prev.next = cur.next
else:
prev = cur
cur = prev.next
return dummy.next
Great tutorials..sharp to the point..two thumbs up!!
there is a bug in this video
while(cur) {
ListNode* nxt = cur->next;
if(cur->val == val) pre->next = nxt;
else {
pre->next = cur; >>> this step is ignored in this video (7:11)
pre = cur;
}
cur = nxt;
}
What app are you using to black board?
If the node you are removing is the head, why would you not just make the head the next element and then nothing changes except the previous head falls off the linked list?
because you will need to write extra two or three lines to update the head pointer each time if the elem to remove is head, it is more elegant and simpler to use the dummy node thing.
Amazing solution, tysm!
Is there something I'm missing in the explanation? This makes sense but when I try this solution I keep running into an attribute error where the list doesn't support the next attribute
Before watching this channel: LeetCode preminum
After watching this channel: Goodbye monthly subscription
I am not sure I understand completely.
What if in line 15: curr.next.val == val ?
never mind. I see: prev.next would be triggered again and so it would skip that value as well.
For JAVA people
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode();
ListNode prev = dummy;
dummy.next = head;
ListNode curr = head;
while(curr != null )
{
if(curr.val == val)
{
prev.next = curr.next;
}
else
{
prev = curr;
}
curr = curr.next;
}
return dummy.next;
}
}
nice explaination😄
Teşekkürler!
This is confusing you say we use two pointers and it seems like the dummy is one of the pointers but then you talk about moving both pointers every time , well then how could dummy point to the head? Sorry i think you are not clear enough
by using the listnode class we are building duplicate linked list awith nor values and then we dynamicallu add the values of that node using the prev and the cur pointer
as you can see that the values in the current node has the actual head value that we are comparing other than that we are just using prev to update the values
i love when u say neetcode problem
thank you so much
public Node removeNode(Node head,int data){
Node temp = head;
if(temp.data==data){
head= head.next;
temp = head;
}
else{
while(temp.next!=null){
if(temp.next.data==data){
temp.next = temp.next.next;
}
else
temp = temp.next;
}
}
return head;
}
this is wrong, if the first two values need to be removed, this would not work.
thanks bro!
This solution doesn't work, all it does is point the prev point to current when it finds a value match in the middle
how is dummy.next is getting updated since we are never updating it?
It points to head which _is_ getting updated.
@@webknowledge9989 where is the head getting updated only prev and curr are getting updated and curr has copy of head if curr is getting updated than how it can update the head
@@mohitsharma38 it's important to understand that you are not creating copies at any point here. The variables are just references to the actual objects (i.e head). You are modifying the contents of the object whenever you edit the object's properties like next and val.
Thank you
why "prev.next = current "
is not working ,it should also work
I don’t understand why he had while curr: as the while loop. Can someone please explain this to me?
this is how you itterate through the linked list, on line 19 he sets curr to the next value and it will continue to the next value until it is NULL ie. at the end of the linked list and the while loop will end.
what do you think of this Python solution? I know it's O(n) time and space complexity but this was my first attempt :)
nums = [ ]
dummy = ListNode()
current = dummy
while head:
nums.append(head.val)
head = head.next
for num in nums:
if num != val:
current.next = ListNode(num)
current = current.next
return dummy.next
thanks a lot
why returning head is wrong?