I am here to show my support, you are really talented at giving a clear thinking process to help people divide and conquer questions that might seem intimidating at the first glance. Good joooob!!
How about this approach .. def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: itr = head if itr is None: return itr while itr.next: if itr.val == itr.next.val: itr.next = itr.next.next else: itr = itr.next return head
this was super helpful but can't you eliminate the need for two loops by doing something like this instead? if(head == null){ return null; } ListNode first = head; while(first.next != null){ if(first.next.val != first.val){ first = first.next; } else{ first.next = first.next.next; } } return head;
@@MahmoudHassan-mm6gz It seems more intuitive to me if you only have one loop. Tbh i'm a bit confused why the solution he gave us used two loops. If you only need to loop through each element once, why use two loops for that?
Technically it's still one loop, so if i rewrite it like this it's still the same code :) cur = head while cur and cur.next: if cur.val == cur.next.val: cur.next = cur.next.next else: cur = cur.next return head
Thank you for the awesome video, just curious if we set the cur node to head initially and iterate through the linked list (deleting repeated nodes as necessary) using cur but return head, how do we know that head has the updated nodes since we performed the deletions on cur and not head? Shouldn't the "return head" command simply return the original linked list? If anyone knows please enlighten me. Thanks in advance
In python assigning one variable to another variable creates an Alias of each variable. An alias is a variable that points to the same object in memory as another variable. Hope that helps
@@eraivansaran5836 Thank you for the clarification, it completely slipped my mind that the cur variable still points to the same memory as the original head object
In worst case, if the Sorted List has no duplicates, could we assume the big O is O(n^2) instead of O(n)? Because head node will be through all nodes which is O(n) at least. The big O should definitely higher than O(n)? However, we know it would not be more than O(n^2) for sure. Please let me know if my understanding is on the right track.
I was about to comment this same! And Yes I guess, in the worst case when there's no duplicate, the TC will me O(n^2) and in good case the TC will lie between (n,n^2) with round brackets, since round brackets doesn't include sensitive/extreme points( ie n and n^2)
If there is no duplicate then the inner while loop won't run. For the inner while loop to run it needs for current to have a next node AND that it's next value is equal to the current value. Think of the inner while loop as an IF statement that triggers for every node. You can actually replace the while loop for an IF ELSE statement and the code will run fine.
your solution is super useful, but here is my solution using only one loop class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head: return head prev = head curr = head.next while curr: if prev.val == curr.val: temp_next = curr.next curr.next = None prev.next = temp_next curr = temp_next else: prev = curr curr = curr.next return head
@NeetCode Please create your own dsa with python course. It will be off the charts there isn't many resources for dsa with python on RUclips. Please man...
If you want a head start there’s a book that gets close and the explanations are great. It’s called Computer Science Distilled it’s very beginner friendly but the code is pseudo due which honestly looks just like python and can help give you an idea on general dsa concepts. If neet does a full course I’d honestly pay for it tho I love this guy
@@Septix yeah thanks for the suggestion although I have the basic knowledge of all data structures but wanted videos on dp, and some graph algos from this channel. Since these topics really important.
as cur is set(=) to head, they are also pointing to the same physical address of a node.. Think like, we have an object of xyz class named b(b=xyz()), and we set a=b. Also supposd In xyz's constructor there is a variable name y="abc" we modified it by a.y="Hello" and if we print(b.y) than also it gives "Hello", means the variable is actually being modified internally also. This is the same case in linked list, we did't performed any operation on head, but we were updating the reference through current/temporary node (cur). I suggest you to run this small code, your doubt will be more clear `class solution: def __init__(self): self.y='a' a=solution() b=a b.y='s' print(b.y) print(a.y)`
Dummy node is good if you may want to change or delete the head node... Instead of treating these cases as edge cases and have many ifs and elses in your code, you can create a dummy node before head, now head is just another normal node... and at the end you return dummyNode.next (the new head)
Can someone please explain why we return head instead of cur? If the input of head is [1,1,2,3,3] wouldn't returning head return [1,1,2,3,3]? The code never modifies the head variable right? We only set cur = head. This is confusing
as the code runs, cur will be incremented down the linked list and eventually cur will equal the last node in the list. If you return cur, you won't have the whole list, you will only get the last node of the list. If you return head, you will be returning the entire list. Cur != head.
The question return type is listnode which points to the revised list head if we return curr it is null which means your done with your question but not delivering the correct answer
Good solution but you could have also remove the appendages(references) of the duplicates to the original list so that garbage collection can do it's job. I know it's not in the problem requirements but one of the reasons we remove duplicates is to free up space but in your solution the same amount of space is still being occupied.
After making the assignment `cur.next = cur.next.next` there is no more references to the node that we "deleted" so the garbage collection will take care of that.
My solution: # Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def deleteDuplicates(self, head): """ :type head: ListNode :rtype: ListNode """ if head is None: return head
first = head second = first.next while second is not None: if first.val == second.val: temp = second.next first.next = temp second.next = None second = temp else: first = second second = second.next return head
It would still be O(n). You could store the values you've seen already in a hash set, and check against that for every node you encounter. This way, you still only take one pass of the array, with a time complexity of O(n) and space complexity of O(n)
2 pointer solution var deleteDuplicates = function(head) { let left = head let right = head while (right) { if (left.val === right.val) { right = right.next continue } else if (left.next.val != right.val) { left.next = right left = left.next right = right.next } else { left = left.next right = right.next } } if (left && left.next) { left.next = right } return head };
hurts to see content like this doesn't get enough support
Your videos literally show that programming is not just about coding.
Thank you.
I am here to show my support, you are really talented at giving a clear thinking process to help people divide and conquer questions that might seem intimidating at the first glance. Good joooob!!
You did a great job breaking this problem down into digestible pieces. Thank you 🙏🏾
How about this approach ..
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
itr = head
if itr is None:
return itr
while itr.next:
if itr.val == itr.next.val:
itr.next = itr.next.next
else:
itr = itr.next
return head
this was super helpful but can't you eliminate the need for two loops by doing something like this instead?
if(head == null){
return null;
}
ListNode first = head;
while(first.next != null){
if(first.next.val != first.val){
first = first.next;
}
else{
first.next = first.next.next;
}
}
return head;
Why would you want to avoid the two loops? it is still O(n) time and O(1) space!
@@MahmoudHassan-mm6gz It seems more intuitive to me if you only have one loop. Tbh i'm a bit confused why the solution he gave us used two loops. If you only need to loop through each element once, why use two loops for that?
Technically it's still one loop, so if i rewrite it like this it's still the same code :)
cur = head
while cur and cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
Thank you for the awesome video, just curious if we set the cur node to head initially and iterate through the linked list (deleting repeated nodes as necessary) using cur but return head, how do we know that head has the updated nodes since we performed the deletions on cur and not head? Shouldn't the "return head" command simply return the original linked list? If anyone knows please enlighten me. Thanks in advance
In python assigning one variable to another variable creates an Alias of each variable. An alias is a variable that points to the same object in memory as another variable.
Hope that helps
@@eraivansaran5836 Thank you for the clarification, it completely slipped my mind that the cur variable still points to the same memory as the original head object
Same question 😆😂
I am starting to think right, thanks to you
Nested while loops work just fine but I prefer just one:
current = head
while current.next:
if current.val == current.next.val:
current.next = current.next.next
else:
current = current.next
return head
while current.next condition itself doesn't work, you need to say while current and current.next:
@@abdifatahmoh Why we have specify both ?
@@vivekanpm3130 cuz we using current and current.next, for current.val == current.next.val
Can you clear why while loop didn’t change anything on head. But head had changed???
With all due respect, imo, this code is a bit simpler to read:
if (head is null) return null;
ListNode back = head;
ListNode front = head.next;
while (front is not null)
{
if (front.val != back.val) back = back.next;
front = front.next;
back.next = front;
}
return head;
OMG finally someone commented on this
I solved it exactly the same way you did and it works fine
In worst case, if the Sorted List has no duplicates, could we assume the big O is O(n^2) instead of O(n)? Because head node will be through all nodes which is O(n) at least. The big O should definitely higher than O(n)? However, we know it would not be more than O(n^2) for sure. Please let me know if my understanding is on the right track.
I was about to comment this same!
And Yes I guess, in the worst case when there's no duplicate, the TC will me O(n^2) and in good case the TC will lie between (n,n^2) with round brackets, since round brackets doesn't include sensitive/extreme points( ie n and n^2)
If there is no duplicate then the inner while loop won't run. For the inner while loop to run it needs for current to have a next node AND that it's next value is equal to the current value. Think of the inner while loop as an IF statement that triggers for every node. You can actually replace the while loop for an IF ELSE statement and the code will run fine.
your solution is super useful, but here is my solution using only one loop
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return head
prev = head
curr = head.next
while curr:
if prev.val == curr.val:
temp_next = curr.next
curr.next = None
prev.next = temp_next
curr = temp_next
else:
prev = curr
curr = curr.next
return head
what blackboard you are using?
@NeetCode Please create your own dsa with python course. It will be off the charts there isn't many resources for dsa with python on RUclips. Please man...
If you want a head start there’s a book that gets close and the explanations are great. It’s called Computer Science Distilled it’s very beginner friendly but the code is pseudo due which honestly looks just like python and can help give you an idea on general dsa concepts. If neet does a full course I’d honestly pay for it tho I love this guy
@@Septix yeah thanks for the suggestion although I have the basic knowledge of all data structures but wanted videos on dp, and some graph algos from this channel. Since these topics really important.
I have a question... In the code , we didnt change the 'head', why it will be changed and be the final answer at the end? Anyone?
as cur is set(=) to head, they are also pointing to the same physical address of a node.. Think like, we have an object of xyz class named b(b=xyz()), and we set a=b. Also supposd In xyz's constructor there is a variable name y="abc" we modified it by a.y="Hello" and if we print(b.y) than also it gives "Hello", means the variable is actually being modified internally also. This is the same case in linked list, we did't performed any operation on head, but we were updating the reference through current/temporary node (cur). I suggest you to run this small code, your doubt will be more clear
`class solution:
def __init__(self):
self.y='a'
a=solution()
b=a
b.y='s'
print(b.y)
print(a.y)`
Can you explain why u are using dummy node 🙄.you used dummy node in merging 2 sorted list.
Dummy node is good if you may want to change or delete the head node... Instead of treating these cases as edge cases and have many ifs and elses in your code, you can create a dummy node before head, now head is just another normal node... and at the end you return dummyNode.next (the new head)
Can someone please explain why we return head instead of cur? If the input of head is [1,1,2,3,3] wouldn't returning head return [1,1,2,3,3]? The code never modifies the head variable right? We only set cur = head. This is confusing
bro cur will be at null why return null, we will return head nah
You have same question as me...
I have replied to someone in the above comment section, if you are still confused you can check it.
as the code runs, cur will be incremented down the linked list and eventually cur will equal the last node in the list. If you return cur, you won't have the whole list, you will only get the last node of the list. If you return head, you will be returning the entire list. Cur != head.
The question return type is listnode which points to the revised list head if we return curr it is null which means your done with your question but not delivering the correct answer
thanks
Java solution: class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode current = head;
if(head == null) return head;
while(current.next !=null){
if(current.val == current.next.val){
current.next = current.next.next;
}else{
current = current.next;
}
}
return head;
}
}
This code does not work for [ 1,1,1 ] test case
Good solution but you could have also remove the appendages(references) of the duplicates to the original list so that garbage collection can do it's job. I know it's not in the problem requirements but one of the reasons we remove duplicates is to free up space but in your solution the same amount of space is still being occupied.
After making the assignment `cur.next = cur.next.next` there is no more references to the node that we "deleted" so the garbage collection will take care of that.
My solution:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return head
first = head
second = first.next
while second is not None:
if first.val == second.val:
temp = second.next
first.next = temp
second.next = None
second = temp
else:
first = second
second = second.next
return head
idk why am i getting a time limit exceeded msg when my solution is literally the same as few solutions in the solutions section, anyone?
If the list was unsorted, what would have the time complexity been? Would it have been O(n^2)?
It would still be O(n). You could store the values you've seen already in a hash set, and check against that for every node you encounter. This way, you still only take one pass of the array, with a time complexity of O(n) and space complexity of O(n)
2 pointer solution
var deleteDuplicates = function(head) {
let left = head
let right = head
while (right) {
if (left.val === right.val) {
right = right.next
continue
} else if (left.next.val != right.val) {
left.next = right
left = left.next
right = right.next
} else {
left = left.next
right = right.next
}
}
if (left && left.next) {
left.next = right
}
return head
};
i love you
This code will not working in geeks for geeks