Clone A Linked List (With Random Pointers) - Linear Space Solution & Tricky Constant Space Solution

Key Takeaways

this is it so if it weren't for this question right here I probably would not be standing in front of you and I would not be teaching today so this is the question that I failed in that one remember that video the how to get a job at Google thing where I talked about failing an interview this is the question Where I Stood at the board I stared at it and I started drawing boxes just black boxes I had no idea how to answer it I had no idea how to approach it I never done linked list problems if it weren't for this question like I said I probably would not be teaching in front of you today all right so our interviewer gives us a question they say we have a linked list so we have a linked list and it's a standard linked list you see node we have a next pointer we have a node we have a next pointer we have a node we have its next pointer every node has a next pointer but it not only has a next pointer it has a random pointer and so these red arrows signify a random pointer so this first node is pointing to the second node it's just random this second node is pointing all the way to the last node and the third node in the list is pointing all the way to the first node so the thing is this complicates things because making a deep copy of a linked list with just next pointers that's trivial that's pretty simple we just make a clone we're advancing on the original list and we just clone each node but with these random pointers what we have to do is we're going to have to connect the Clones we're going to have to connect the clones and their random pointers into the same random assortment so that presents us a difficulty that is the roadblock my brain hit I cannot even recognize that roadblock so the key is we find our roadblocks first we have a linked list problem normally linked list problems are going to run in linear time and constant space so that's going to be the case for this problem the best solution is in linear time and in constant space we're going to look at all of those solutions for this problem today so before it even start with the actual question and going into the solutions I want us to first hit the mental barrier I want us to find where our mind gets stuck in this question and use what we know to try to clone this list and see what happens all right so whenever we Traverse a linked list or any singly linked list doua link list it's all about pointers it's all about using pointers and advancing them as we do copies so let's set a pointer on the first item so now we have a pointer on the first item and let's make a copy of it okay so that makes sense so we can't really do a copy of the random pointer because we don't even have that node yet in our clone list so now let's Advance our next pointer and let's just continue copying let's see where this takes us okay and now we're looking at this node and now we're going to copy this node so let's make it copy and what however we implement this it would be pretty straightforward we would connect these two noes and now this is where we hit a mental barrier this is what happened in my interview I knew that I needed to do pointers okay I know how to work with singly length list but I hit a mental barrier wait when do I connect these random pointers how do I get from my original list to my clone do you see how I'm starting to cook up problems do you see I'm starting to think wait how is this going to be wired okay I may be able to clone the list and give it next pointers but that's not what this problem is about these random pointers give me trouble getting to this mapping in constant time is giving me trouble do you see these thoughts these are the key things you need to vocalize these are the key things you need to watch you need to watch these things and see them because will help you get to the answer so the thing is with these questions there's what we already know and the connections we can draw so we already know how to do normal iteration with a link list but I would have to say that if you've done enough problems and enough practice you might already know how to clone a graph by this point so if you can clone a graph do you remember back to how we did that we want constant time access into these clones to do a mapping and it makes the mapping much easier to do so what data structure does that make me think of what what solution strategy do I remember well I could use a hash table I can use a hash table to have access to this clone list so that one I can make these mappings I can have constant time access to these mappings from an original node to a clone and then not only that I can reach this node and then I can set the random pointer of the Clone node by reaching to the random pointer of the original node and then I can reach its clone in constant time so that is the utility of a hash table and that is how we're going to have a linear space solution so let's walk through the linear space solution as always code is in the description I would read the code first or watch this first it's however you learn but we have the code so let's walk through the linear space solution all right so now let's look at the linear space solution both Optimal Solutions are going to be linear in time we're going to have to touch every node in the original list we're going to have to expand linear time in order to make a deep copy but where we can optimize is space so we're going to do linear space because we're going to hold a linear amount of mappings when this list gets arbitrarily large our mapping amount is going to scale in a linear fashion so what we're going to do is we're going to do two passes on our first pass we're going to create every mapping I will connect nothing no connections will happen and on the second pass when all my nodes exist and all my clone mapping exist I will be able to iterate over the original list and I can snatch the Clones through the hashmap the hashmap lets me snatch the Clones so let's go through this and you'll see what I mean so now we're going to put an iteration pointer on the first node okay so an iteration pointers on the first node let's make a copy of it and remember this is a hashtable mapping we have map the original node to its clone so we're going to be able to reach right in and do any operations we need on the new list being built this is the utility of a hash table so we can advance our pointer and now we can make a copy of that node we've Advanced the pointer again and now we make a copy of this node and now let's Advance it again and now let's make a copy of this note so what is going on here's our original list is wired up in memory here's our new list and we have all these notes just sitting dead in the water sitting dead in the water in memory unconnected no pointers connecting them in memory and that is where these notes are sitting this is our first passes job what our hashtable does is when I have a reference to this node constant time access into its clone when I have a reference to this node constant time access into its clone that is what our hash table does it's mapping allows us to execute rewirings very efficiently so now what we do is we do a second pass I'll put my iteration pointer on the head okay so on pointed here my job at each of these nodes is to populate the next field and the random field so what we need to do is how do I populate this clones next field remember our hash table is giving us access to this clone so this node we're going to have to say this node's clone hash table give me the Clone okay I have the Clone now this clones value. next is going to be this node how do we get to this node k. next k. next in the Clone map and then we're going to wire those together again code is in the description I look at the code first before you hear me say it in words because it's easier to understand the words once you see the code it's more structured so now what we're going to do is do that wiring and so now we need to wire the random pointer so we see that the original random pointer does this right so what I say is go through the Clone mapping I'm at this guy I went to set as random so I'm right here and now what I need to do is I need to go original Curr node. random I'm over here what do I do I hop to its clone this node's clone right here and now I have reference here now I have reference here and I connect them this is it this is our algorithm we're going to do this for every single node and remember our mapping is giving us this utility it is giving us this constant time access I'm going to keep saying it into its clone if we have reference here we have reference here in constant time so now let's Advance our pointer and move forward in the list and so now we're pointing to the next node in the original list so again jump down to the Clone we have reference to that and then jump to the random in the original list and then we have access to this clone and now we can wire these guys together and then again we would do the next wiring and now we can advance the pointer to the next node I'm sorry this is kind of getting sloppy but you should get the idea so now we want to wire the next again hop down them into the Clone and then what we do is go next and hop down to this clone and now we can connect these all right and now we can do the random connection we go to this node we hop down we have this clone and now we go to its random which is over here and then we have this clone so now we can connect this this guy to this guy and then finally we advance to the final node and then what we do is we copy it next which is just null and it has no random value so we wouldn't even copy that random value so this is how we take a deep copy of a link list with random pointers it's all about making the mapping first making all of these notes and then executing the connection of pointers in our clone list because we have access to our clones from each of the original nodes and when you do that it's very simple the linear space solution is very straightforward so we can get a little tricky we can improve our space complexity this this is probably not going to be something you're going to execute in an interview but I want to show you it just so that you are aware of this and that most of these problems have Optimal Solutions that are kind of Out Of Reach sometimes in the time of an interview but are still interesting to know because it could express some some extra degree of problem solving ability but to be honest it's it's still kind of up in air so if you're uncomfortable with linked list problems definitely check the code in the description the constant space approach will definitely take you for a ride and you are going to get confused very quickly but give it time read the code over several times and you will eventually just understand it you're going to see it's just rewiring things we just need to keep track of how we rewiring pointers it is nothing more than that we're going to spend linear time and do constant space so now remember this is going to be linear in time because we're going to expand linear time going through the original list and linear in space because we're going to be storing and mappings we're going to store a mapping to each nose clone this is not including the output which is going to be o of n because we're going to have to have a linear amount of clones but what we can do is we can improve the space we can improve the space to constant space so I want to show you that approach as well and I definitely again want to warn you it's going to be tricky okay so now we're going to look at the constant space solution and we're going to see how we're going to do this so we're going to set a pointer on the first note of the original lists and let's see where this takes us I'm going to create a copy node in memory let's do that right now and remember at all times I want you to think of mental barriers when we use constant space what is the mental barrier that I face well if I'm using constant space I can't keep mappings I can't have a I can't have a hashmap to map to this clone how am I going to get access to the Clone and it's a little trick that we use what we do is utilize the next field on the original node to map to its clone so we bridge the gap like this do you see how I just pointed the original node's next field to its clone and now what we're going to do is we're going to point the next field of the Clone node to the next node of the original node so let's do that and remember how I said this is all about rewiring this is where things get tricky I need you to stay with me so all we did was we pointed the next field of the original node to the mirror node and we pointed the mirror node to the original node's next node the thing is we need to restore the original links list the reason we do this is because we're going to need to restore these pointers we need the original node to point to its clone but what we do is we cannot screw up the random pointer and we need to restore the next field at the end so what we do is we remember the original nose next node on this mirror node so again read the code and follow this description but again this is tricky at first take your time but it will make sense so now we're going to go to the next node and again this is still our first path and what we're going to do is we're going to point the original nodes next to its clone and then we're going to point this next value to the original nodes next and now we're going to advance our iteration and then we're going to create a clone and rewire this next to that clone and what we're going to do is we're going to point the copy nodes next to the original noes next and then we'll Advance our iteration and then we're going to create a clone and now we need to adjust the next to point to the Clone and now we need to get the Clone to point to the original nodes next which is just null so this is our first pass so what did we just do what we just did is we created a clone mapping and now we have not used any additional space but now we have access from the original node to the Clone node so now we have to do a second pass so now the second pass's job is to do what we were doing before we want to fill in the random pointers and now what I'm going to do is I'm going to set an iteration pointer at the first node and now what I'm going to do is I'm going to reach to c.ex that is my clone c. next. random I want to set that I want to set the random pointer for this node what do I set this random pointer to for this node I go curve. random curve. random. nextt what is that the clone of the original original nodes random so now I have this node I have this node and now what can I do I can set the random mapping do you see mapping we can set the mapping so that is how we do it let's set it and again this is probably going to get sloppy so definitely check the code out but I still want to do this walkthrough so now what we just did is we did our job and how do we get to the next do you see how we destroyed the original node's next value by mapping to its clone how do we get to the next value well I can go next. next that was the point that's why we did that that is why we stashed the next value of the Clone as the next value of the original so we can go c. next. next and now we're at the next point in our iteration let's do it now we're right here and we do the same thing c.ex is right here and c. random. nextt is right here connect them okay and now what we can do is we can advance c.t. next and now what we can do is c. nextt we're right here and now we can go c. random. next we're here so connect these guys and now we can go c. next. next get to him now we have the last note and now we can set the random value there's no random value to set so now we can advance and then we hit no and we're done with our second pass so guess what our clone is fine our second list is finished but do you see a problem here do you see how we messed up the next node to create a mapping to save space to keep ourselves constant space the thing is we can't just screw up the original caller list we have to restore their list so what we need to do is we need to go back and do a third pass the first pass job was to create the mapping to our clones the second passes job was to fulfill the random pointers and the third pass's job is going to be to restore the original list and then reap the final list so what we need to do is restore the original list but the thing is this is pretty straightforward because remember we have access to the next node of each of these original nodes all we need to do is go c. next and then the next value of the Clone is the next value of the original because we stashed that so why don't we just restore that again the code is in the description and it's fairly straightforward to do the restoration and so after our final pass we're going to rewire each of those notes to the original next and we're going to rewire each of these new nodes to their next nodes which we're going to have access remember we can go Cur on next to get the Clone so the next of him is going to be this guy's next value that is how we do this problem in constant space so would we have to do this in an interview probably not but I wanted to show you it and give you a code sample in the description just so you are aware of it so this is this problem this is the problem that took me down and eventually I learned it and I think you can learn it too if you take the time to read these problems over realize that most of these problems are linear time and con of space and all about rewiring and working with pointers the more you do the better you get it is that straightforward so that is all for this video If you like this video hit the like button subscribe to the channel this channel is about empowering software Engineers to excel in the interview and do their best so that is all for this video and we are done [Music]