Great job! Thanks for the video. This was asked in my friend's Adobe interview. Also, if the original list is required to be retained as before, original->next = original->next->next->r
Wrong approach this approach will work with hashmap only . Bcoz next of original LL is lost so how we r going to traverse next in original Linked list ????
@vivekanand khyade great work. can you add your github repository link description instead of writing on board that will increase your views and clarity .
I can explain the logic. For the cloned list, don't make next pointer point to next node in cloned list as mentioned in this video. Instead make it point to original node next. For example if original node layout is n1-->n2-->n3 and cloned node layout is n11-->n22-->n33, then the list will be n1-->n11-->n2-->n22-->n3-->n33. This chain is formed by connecting next pointers. Later you can split the original and cloned node list by walking through the list and moving the next pointers. Hope this helps.
Sir your videos are great. Thank you for uploading insightful videos . Could you please organize your videos in a youtube playlist , So that , that will be easy for a new viewers to watch the videos in a sequential manner. Anyway Great Initiative really appreciable.
But I have a question. You have modified the next pointer of original List , how will you traverse the original list if asked to ? We are not supposed to modify the original List.
Please, correct me if I am wrong, Next pointer of original Linked List still pointing to cloned Linked list nodes.We have to assign them back to their original nodes.
I don't understand... can't you just keep iterating to the next and set the new linked list each node's random equal to the above random? node 1: certain next, certain random copy: certain next, certain random go to next node node 2: next, random copy: copy next, random so on and so forth
it songs nice to listen, but there is a problem with this approach, at 2:07 you are mentioning that you will assign the next for original list to the newly created list, but in this case you are detaching the original list with its own next, so on the next iteration how will you traverse to the original list next points. gotcha :)
No i think you got it wrong his approach is correct to solve this question, but the problem arises when the interviewer asks not to modify the original list then you might want to look for another approach.
this approach doesn't work entirely actually. If you notice your modifying the pointer of the original LinkedList (the next pointers in particular) and when I submit the implimentation to leet code it is complaining with the following: "Next pointer of node with label 7 from the original list was modified." I also later tried copying the original linked list again (2nd copy) later to use that 2nd copy to set the next pointers of the original linked list back it is still complaining with the same issue. Any suggestions with this? I dont want to solve it with a hashmap.
czcams.com/video/OvpKeraoxW0/video.html See the comment section you will find code as well. Let me know if you have some doubt. I will help you in understanding.
This particular solution destroys the old list and also the whole point of creating a copy of a list is that we have both the copies of the list intact(no changes made to the old one) ....so we cant implement this in real case scenarios....the trick was quite impressive but still there can be other solutions too....
i am not getting one thing sir.. why cant we just copy reference of random pointer like how we copy data from other node. traverse both at a time head = original copy = copied traverse both at a time copy.randomPointer = head.randomPointer head= head.next copy = copy.next ... whats wrong with doing like this ??
Because if you have A->B->C->D and A.random = D, then after you'll copy, you'll have, let's say, a->b->c->d. But a.random will be equal to D, not d. That's way it's not okay.
we recover the original list. Suppose if you are at first node of clone list , Before setting the random clone->random->next=clone->next->r; Then after this you can set your random pointer
sir I didn't understand the problem yet because In linked list each node has two fields first is for data and second is for the address of the next node but here there are three fields for node, random pointer and next pointer ?
this is not the right method you can't recover the original list with this approach. I will say use the next of clone and point it to next original object and make a garland of the old and new list and then recover the old and the new
Sir there is one request to is...that before solving with one of the best algo ...plzz go through the nive once just to let us grasp the power of developing algo not just copying optimized one...i know you can do this better..and will help every one big time..looking forward to see you in some of most interesting videos.....:)
The step used here is wrong: Use the below link to understand and code:- czcams.com/video/OvpKeraoxW0/video.html Follow this approach in the given video. You can check the code in comment section. The mistake is we are changing the next address which will further destroy the original list.
solution in python def copyList(self, head): d=dict() head2=None temp=head while temp: d[temp]=Node(temp.data) if not head2: head2=d[temp] temp=temp.next temp2=head while temp2: d[temp2].next=d[temp2.next] if temp2.next else None d[temp2].arb=d[temp2.arb] if temp2.arb else None temp2=temp2.next return head2
This is a neater solution - def copyRandomList(self, head): from collections import defaultdict d = defaultdict(lambda: RandomListNode(0)) d[None] = None m = head while m : d[m].label = m.label d[m].next = d[m.next] d[m].random = d[m.random] m = m.next return d[head]
I was asking myself the same question: what's the point of creating this "copy" if we destroy the original. Does anyone accept this as a valid solution anywhere?
I Have written the code for what he has just explained .He missed out a little bit of more explaination but i got it . Take a pen and copy and start drawing its traversal Hope it helps !! :-) Node *copyList(Node *head) { if (head == NULL) return head; Node *t = head; while (t != NULL) { Node *n = new Node(t->data); n->next = t->next; t->next = n; t = n->next; } t = head; Node *head2 = head->next; while (t != NULL) { if (t->arb == NULL) t->next->arb = NULL; else { t->next->arb = t->arb->next; } t = t->next->next; } t = head; while (t != NULL) { t->next = t->next->next; t = t->next; } return head2; }
Every tough question out there is explained by Vivek :) Thank you very much !
its good to see such a good video and you are still uploads videos today!
Was asked this in my Google interview
@@prabhatkashyap8333 when should we use had been
are you still working in Google?
Thank you for posting the videos!! They are super helpful!
Thanks. Thats very clear and awesome.
THAKN YOU SOSOSOSOSOS MUCH ! WAS STRUGGLING SO MUCH WITH THIS QUESTION ! ! ! !
FINALLY UNDERSTOOD IT
CANT THANK ENOUGH ! ! ! ! ! ! ! !
Easy to understand solution ! Thanks Vivekanand !
Great job! Thanks for the video. This was asked in my friend's Adobe interview. Also, if the original list is required to be retained as before, original->next = original->next->next->r
Thanks a lot for explaining in such easy way
Wrong approach this approach will work with hashmap only . Bcoz next of original LL is lost so how we r going to traverse next in original Linked list ????
Thank you for such a good explanation.
Thank You Sir!
Very well explained.
@vivekanand khyade great work.
can you add your github repository link description instead of writing on board that will increase your views and clarity .
amazing and very clear explanation.
Very helpful! Thanks Vivek!
Thank you friend :)
very clear explanation, if you can add the implementation in Java will be wonderful.
Such clear explanation...🙏🙏
He is a great teacher but sadly an underrated teacher :(
The question, that I thought was too difficult
Now I think that's too easy .
Thank you sir
Very easy to understand love you
brilliant solution for O(1) space
using this approach, how can you reconstruct the original list so it will not be lost?
I can explain the logic. For the cloned list, don't make next pointer point to next node in cloned list as mentioned in this video. Instead make it point to original node next. For example if original node layout is n1-->n2-->n3 and cloned node layout is n11-->n22-->n33, then the list will be n1-->n11-->n2-->n22-->n3-->n33. This chain is formed by connecting next pointers.
Later you can split the original and cloned node list by walking through the list and moving the next pointers. Hope this helps.
@@babusingarayan7325 Very important! Thank you for the explanation
Sir your videos are great. Thank you for uploading insightful videos . Could you please organize your videos in a youtube playlist , So that , that will be easy for a new viewers to watch the videos in a sequential manner. Anyway Great Initiative really appreciable.
yes sure Yureka.....i will do it soon.
Simple and crisp explaination.
Excellent explanation
Thanks alot!! :)
you are awesome..thank uu
great work sir , please upload more video on interesting question on linked list . thanks
Thanku soo much for making all d concept clear
But I have a question. You have modified the next pointer of original List , how will you traverse the original list if asked to ? We are not supposed to modify the original List.
great sir....maza aa gaya
Very Clear and crisp explanation Sir. Always loved your videos because of their simplicity .
Beautiful
How do you assign copied LinkedList random node to original in code?
Underrated
Is this the only way to clone a linked list,can it be done without random pointer?
What about those broken links in original list?
exactly.
thank you kind sir
You should have explained also the part where we restore the original linked list pointers !
Please, correct me if I am wrong, Next pointer of original Linked List still pointing to cloned Linked list nodes.We have to assign them back to their original nodes.
Yes Rudraansh , you are right. You have to set the pointers as they were before cloning. Thanks for helping me to improve.
No, you have to do
cone.random.next = clone.next.random;
clone.random = clone.random.random.next;
How to recover the original list. Not sure if this is the right method
very good explanation
Awesome!!
why youtube is not recommending this video
But u didn't Point the next Pointer of Original DLL to the Previous Position.
Clear exposition, however you should include how the next pointers of the original list are restored because the original list should remain intact.
In that case, there's another approach using hashmap/dictionary with 2 scans of the list and O(n) space
Amazing !!!!!!
thanks sir.
Sir what about copying in single linked list
I don't understand... can't you just keep iterating to the next and set the new linked list each node's random equal to the above random?
node 1: certain next, certain random
copy: certain next, certain random
go to next node
node 2: next, random
copy: copy next, random
so on and so forth
it songs nice to listen, but there is a problem with this approach, at 2:07 you are mentioning that you will assign the next for original list to the newly created list, but in this case you are detaching the original list with its own next, so on the next iteration how will you traverse to the original list next points. gotcha :)
No i think you got it wrong his approach is correct to solve this question, but the problem arises when the interviewer asks not to modify the original list then you might want to look for another approach.
@@ansar2137 we can again rebuild the original list by orginal.next->original.next.next.random
I think so!!
this approach doesn't work entirely actually. If you notice your modifying the pointer of the original LinkedList (the next pointers in particular) and when I submit the implimentation to leet code it is complaining with the following: "Next pointer of node with label 7 from the original list was modified."
I also later tried copying the original linked list again (2nd copy) later to use that 2nd copy to set the next pointers of the original linked list back it is still complaining with the same issue. Any suggestions with this? I dont want to solve it with a hashmap.
czcams.com/video/OvpKeraoxW0/video.html
See the comment section you will find code as well. Let me know if you have some doubt. I will help you in understanding.
This particular solution destroys the old list and also the whole point of creating a copy of a list is that we have both the copies of the list intact(no changes made to the old one) ....so we cant implement this in real case scenarios....the trick was quite impressive but still there can be other solutions too....
great explannation
tkanks buddy
So how do you restore the original list? The next pointers are fucked!!
Hi Will , you are correct. We have to store the mappings of the original linked list if we want the original linked list intact even after cloning.
original->next = original->next->next
where can i find the code? Please tag anyone.!
Hope it helps:
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
class JavaSolution{
public Node copyRandomList(Node head) {
if(head == null)
return null;
//create copy of nodes
Map map = new HashMap();
Node current = head;
while (current != null) {
map.put(current, new Node(current.val));
current = current.next;
}
//fix next and random pointers
current = head;
while (current != null) {
map.get(current).random = map.get(current.random);
map.get(current).next = map.get(current.next);
current = current.next;
}
return map.get(head);
}
}
good job
how to add two different linked list
i am not getting one thing sir.. why cant we just copy reference of random pointer like how we copy data from other node. traverse both at a time
head = original
copy = copied
traverse both at a time
copy.randomPointer = head.randomPointer
head= head.next
copy = copy.next ... whats wrong with doing like this ??
Because if you have A->B->C->D and A.random = D, then after you'll copy, you'll have, let's say, a->b->c->d. But a.random will be equal to D, not d. That's way it's not okay.
was this really this easy ?
thank you sir :)
Amazing
Unable to get understand this concept..but .all the other videos are awesome
Upload about Circular Linked Lists
We would be essentially destroying the 1st linked list with this method
we recover the original list. Suppose if you are at first node of clone list , Before setting the random clone->random->next=clone->next->r;
Then after this you can set your random pointer
sir I didn't understand the problem yet because In linked list each node has two fields first is for data and second is for the address of the next node but here there are three fields for node, random pointer and next pointer ?
No, we can customise the nodes in the linked List. Here . it is customised for 3 fields.
N.K.Sunil Sunilnk okay thanks
N.K.Sunil Sunilnk
8250290061
Cll me plzzzz
this is not the right method you can't recover the original list with this approach. I will say use the next of clone and point it to next original object and make a garland of the old and new list and then recover the old and the new
+1 for this comment.
Original node got destroyed.
The original list is not destroyed. It is just a copy of that list being created.
@@PrasannaLakshmi74 He has updated the next pointer of original list to point to copied list, in this you won't be able to recover original list.
Thank you, sir , good explanation.
thanks sir
We can't recover the original list..........
Nice
can we also clone binary tree using same method!?
i will study that and let you know in this week..
To clone a binary tree just do a pre-order traversal of the tree.
Hitesh Dayaramani
Hlw
👍
It would have been better if you provided the psuedo code as well
Sir there is one request to is...that before solving with one of the best algo ...plzz go through the nive once just to let us grasp the power of developing algo not just copying optimized one...i know you can do this better..and will help every one big time..looking forward to see you in some of most interesting videos.....:)
Thanks Ankit.
can you share program also?
The biggest problem in this algorithm is that destroyed the original linkedlist
yep exactly and leet code does not accept this as a solution
Can anybody give code for this approach
That is such a bad solution u cant link next to node of other linked list because then you wont be able to traverse the linked list!
would you please provide python code for this problem witch is related
Please share code for same.
can anyone give me code of this solution ?
The step used here is wrong:
Use the below link to understand and code:-
czcams.com/video/OvpKeraoxW0/video.html
Follow this approach in the given video.
You can check the code in comment section.
The mistake is we are changing the next address which will further destroy the original list.
very clear but a lit too slow
solution in python
def copyList(self, head):
d=dict()
head2=None
temp=head
while temp:
d[temp]=Node(temp.data)
if not head2:
head2=d[temp]
temp=temp.next
temp2=head
while temp2:
d[temp2].next=d[temp2.next] if temp2.next else None
d[temp2].arb=d[temp2.arb] if temp2.arb else None
temp2=temp2.next
return head2
This is a neater solution -
def copyRandomList(self, head):
from collections import defaultdict
d = defaultdict(lambda: RandomListNode(0))
d[None] = None
m = head
while m :
d[m].label = m.label
d[m].next = d[m.next]
d[m].random = d[m.random]
m = m.next
return d[head]
Code plz
This approach is really bad because it destroyed the original linked list by messing up the next pointers
I was asking myself the same question: what's the point of creating this "copy" if we destroy the original. Does anyone accept this as a valid solution anywhere?
You can store the initial values of next in an array and restore them at the end
I Have written the code for what he has just explained .He missed out a little bit of more explaination but i got it .
Take a pen and copy and start drawing its traversal Hope it helps !! :-)
Node *copyList(Node *head) {
if (head == NULL) return head;
Node *t = head;
while (t != NULL) {
Node *n = new Node(t->data);
n->next = t->next;
t->next = n;
t = n->next;
}
t = head;
Node *head2 = head->next;
while (t != NULL) {
if (t->arb == NULL)
t->next->arb = NULL;
else {
t->next->arb = t->arb->next;
}
t = t->next->next;
}
t = head;
while (t != NULL) {
t->next = t->next->next;
t = t->next;
}
return head2;
}
WRONG
What is the point of creating a clone, if you destroy the original one in the process
Sorry...I failed in understanding this