Skip to main content
Loading Explore guides…
Linked Lists · Acedra
Home
Explore
Computer Science
Linked Lists
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
215 segments
Copy
Hide video
0:00
A linked list is a common data structure used in software development. It is also a frequent topic in technical coding interviews. In this course, Alvin will explain linked lists and prepare you to use them both in interviews and coding projects.
0:18
Hey, programmers, Alf Infrastruktur, here, welcome to our course on linkless. What I want to do is really get you well prepped for those linkless problems on your technical interviews. So consider this a little bit of a crash course, like I do in all of our data structure and algorithm courses, I want to go through two pieces of information for every single problem. That is I want to really
0:36
draw things out visualize things and understand the theory behind a problem before I go ahead and implement the code behind it. Right, so we're gonna do a one two punch for every single problem here. So this is going to be an introductory course on linked lists. So I'm going to assume you know nothing about linked lists, but you're not a total beginner to programming, right. So you understand things like a while loops, for loops, if statements and all that jazz, I'm also going to
0:59
assume that you know, a little bit of recursion, because I'm going to show you some recursive solutions for many of our linked list problems. And so without further ado, let's jump right in. So what I want to do is start by understanding what a linked list is at a high level bird's eye view. The first thing we'll need to know is that a linked list is a type of data structure, right? So we're organized as data. And in particular, a linked list is made up of
1:20
many nodes. So as the first checkpoint here, we need to first understand what a node is, you can think of a node as just a container for some data. So when we conceptually visualize nodes, you really think of them as some circles that I can put some data inside here, I'll put a letter or character inside of my node. But of course, you can store any data you like. It could be a strings, numbers, Boolean, or even other objects, right. And I'm saying that
1:44
a linked list contains many nodes. So let's say had a bunch of nodes, and they can all contain different pieces of data. So I have the characters ABCD, stored in different nodes over here. And if I wanted to make these nodes comprise a linked list, then what I need to do is add some links. In other words, if I have a node like a, I can make it point to the next node, the dataset, that is a points to B, right, can also say that B points to C, and C points to D, right. And the
2:14
term we actually like to use for this is really saying that A is next is B, right? It's going to be very common linkless terminology, and a pattern we're definitely going to see in the code later on. And now you can already see why you call this data structure, a linked list, right, have a bunch of nodes linked together. The important thing to note here, it's about the last node D, right? D is the last node in our linked lists. And so under the hood, we can really represent it
2:37
being the last node, by having its next pointer pointing to nothing or more programmatically, you can have its next set to null, right, the null pointer and whatever your language of choices. So sometimes during this course, I'm going to explicitly choose to dry out the null note or the null reference, just so that we can build some very robust code. Alright, now that we know what a linkless looks like, I want to introduce some other terminology
2:59
that you're going to hear, right. So when we refer to the very, very first node of linkless, that is the a node in this diagram, I consider that the head, it's a very common term. And a similar way, we can refer to the very last node in a link list as the tail, right. So if you hear those words, in problems, we're referring to the first node and the very last node respectively, right? If you think about it, because I have this sense of different nodes, and you know, a first
3:25
note and a second node, but you can think of a linked list as an ordered data structure. In other words, if I started at the head of the linked list, I can just look at this nodes next pointer, and I can go to the B node, so I can just move to the right. And once I'm at the B node, I can see that b has an X that goes to the C node, and the C node goes to the D node, and the D node goes to the null node, which must mean that I'm at the end of the linkless. So that's a very,
3:50
very key characteristic about the linkless. Right? A nice property to leverage about a linked list is that it's an inherently ordered data structure, right? If you want to refer to like the positions of these nodes, and we do that programmer thing of starting at zero, I can see that the head has a position of zero, B has a position of one, and then we just go sequentially throughout, right.
4:10
So there are four nodes within this linked list, I can see that the position of the head is zero, and the position of the tail is three. So so far, we're probably not seeing the full value of the link list, like when would this data structure have some real utility over other data structures that we know about? In other words, you're probably wondering how a linked list compares to an array because an array is also an ordered data structure. So let's do that comparison right now.
4:35
So here I have my linkless up top, if I wanted to represent you know, a similar data structure, but in an array form, it would look something like this, right? I have an array in memory. And I know that that array has some indices, right. So this is a really clear analogy here. I know that the indices of an array correspond to the positions of the nodes of a linkless. Right. And obviously my link was is made of many nodes. Whereas my array has many elements.
5:05
The most important difference between an array and a linked list is that an array must be stored contiguously in memory, that means all of your elements in an array are going to be stored like right next to each other in your computer's memory. And that has a lot of consequences in the runtime of different operations across your array. Right? So let's say right, now I wanted to step through a scenario, let's say I have the goal of inserting a new element Q at
5:30
index two of my array. And the key specification here is I want to insert Q at position two, I don't want to overwrite the current element at position two, right? So at the start of this operation, I have four elements in my array ABCDE. After I do my insertion of Q, I should have five elements in my array, and they should go A B QCD, right, because I'm inserting some new element at index two. So how will this algorithm run at a higher level in an array? Well, typically, all
6:01
you need to do is obviously find the index two, which is right here. And I know that this is where I need to put the new Q element, but I can't just overwrite this value of C, because I want to do an insertion not overwrite. And so what happens under the hood in your programming language, when you perform this insertion operation? Well, we hope that there's still some empty space in the array,
6:21
and it should occur after D, right. Assuming that there's still space in this array, I would need to shift all of the elements to the right over by one index. In other words, I need to put d to the right, I need to put c over a one position to the right. And now I have perfect room to add this cue at index two. Right. And of course, now D would be occupying a new index of four logically. But the
6:46
important step we took here was to actually insert somewhere in the middle of an array, that could mean that you need to shift over a bunch of different elements in your array, right. So in this very small example, I only had to move over to elements of C and D. But let's say you had a very long array, and there were, I don't know, 1000 elements after your insertion index, you would have to shift all of them over one by one. And that is a relatively costly and slow operation
7:13
for such a simple move of inserting Q, right. So we say that when we insert into an array, that does have an O of n insertion time, right, in the worst case, if you insert at index zero of an array, that is you're inserting a very first new elements, you would have to shift everything over by one index in the array. And since there are n elements in the array you're doing and different shifts. Awesome. Now let's compare that to a similar insertion operation for our linked lists.
7:41
So let's say I still wanted to insert the value of queue at position two of my link lists. Well, that means I need to create a new node in memory. And what's great about a linked list is it is not required that the nodes are contiguous in memory. In other words, we can have these like nodes exist anywhere in the space of our computer's a memory addressing. And that's kind of a very low level statement. But the consequence of this is I don't need to do any
8:08
shifting when I perform this insertion. In other words, how does that work? Well, if I want Q, to be composition to have my link lists, now that I've created the new Q node, I just need to adjust B's next pointer. So I'm going to look at node B, and reset its next pointer to point at q, then I set Q's next pointer to point at C. And with those small changes, I've actually changed, the logical order of nodes within my linked list would now be this.
8:38
Right, queue occupies position to see occupies position three, and so on. And what's really great about this is, let's say that there were many nodes after my insertion position, let's say there were 1000 nodes, but wouldn't have to actually modify all 1000 nodes that came after my insertion point, I just need to change about two pointers every single time. Because that's a constant number of operations. I will say that a linkless insertion, if we write it correctly,
9:03
will be constant of one time. So here we see a very tangible difference between our linked list data structure and our array data structure. And there are many more a different pros and cons between these two. But for now, we'll leave it at that and we can chat more about them as we go throughout the course I'm sure it's going to come up. But what I want to do for now is talk about the core core core, a linked list algorithm that's just traversing through a linked list.
9:29
In other words, how can we just touch and process every node within a link lists? Well, the important thing to know is if you wanted to, like give a link list to someone or in other words programmatically pass a link list into a function, you really only need to pass a reference to the head node of a linked list. Because if I give you the head node of a link lists, by accessing the next property of every node, you can have access to the full
9:55
sequential list, right? And so to actually implement a traversal algorithm on a list list, we just need a handful of variables. Most importantly, we need like a current variable, a current reference to look at the current node of the linked list we're iterating through, right. So if I have this current node of A, and I want it to go to the next node, I can just look at current dot next, right or something similar in the programming language of your choice,
10:20
I can just set current equal to current dot next, then I would be at the B node. And B also has an XT. So I do that again, at the C node, I can just keep continuing this process, right, assigning current equal to current dot next, until at some point, once I'm at roughly the tail,
10:39
current would be D. And so current dot next would be this null node or this null reference. And if I set current equal to next, I'll be right at null. And that can be a perfect condition I can catch. In other words, we can stop the algorithm when current is equal to null, we know that that point would have visited every node of the link lists. So as I went through this high level trace,
10:59
I was kind of speaking upon this algorithm as if it was an iterative solution. And I'll also show you how you can solve this one recursively, it's really the same line of thinking. At this point, I would want to actually hop into some code. So we can see the nuts and bolts implementation of a link list as well as the core traversal algorithm through a linked list. Alright, let's do this. So here I am, in my text editor, I'm going to be doing this in JavaScript,
11:22
although you shouldn't be able to follow along in your language of choice. So the first thing I want to do is just manually build a linked list. And to start, I'm going to need to create a node class, right, so we're gonna stay a little bit object oriented here, just create a node class. So from JavaScript, I need to give it a constructor. And in terms of the properties, we're going to need to store inside of an instance of Node, I only need two things, I need to store
11:46
the actual value. But I also need to store a reference to the next node in the linked list, if there even is an x node, right. So to my constructor, I'm just going to take in the value, so I can say this dot val equals Val. And I'm just going to always initialize my next to be null, right, I can just manually reassign this next property. And if you have this class or in it, that's all you need to start creating some linkless. I'll be it manually. So let's say
12:15
I want to construct a linkless, I'll just create a few instances of nodes, I can create node A, make it a new node, I need to pass in the value to be constructed, I'll just give it some characters here, maybe some capital letters this time. So the character a lot create a bunch of nodes like this,
12:32
it's will have my B, my C and my D. I'll give them some corresponding values. Naturally, I'm storing strings or characters within the values of my linkless. But you can make them you know, numbers, if you want, it's no big deal. What I want to do now is actually link these nodes together, that way, I can just have a linked list, I can start writing a few algorithms on, right. So typically,
12:54
this part would be kind of taking care for you already. If you're on an interview, you can assume that you're taking in a properly structured link lists. But if I want to just like test some code for myself, what I can do is say things like A's next is going to be equal to the B node, right. So I'm making A's next property, now become the B reference. So I'm actually linking these two nodes
13:16
together, right? A's next is pointing to be the same way, these next is pointing to C, C's next is
13:23
pointing to D. And there is no other nodes in my linked list, I'm going to leave D alone. Because I know automatically, these next would currently be pointing to null, which does represent the tail of my linked lists. So like visually, I think of this sort of structure, I have a is my head, that points to B, which points to C, which points to D. And technically, D points to like, no, so I'll be explicit here and just draw that one out. Nice. So now that I have my
13:52
link list ready to go, let's go ahead and write our traversal algorithm on it. That is I just want to iterate through every node of the link lesson, maybe just print out the value, something very, very foundational here. And so all maybe choose to make this its own function, I think that'd be the best way to go about doing this. So I'll create a nice function here, I'll call it just print
14:14
linked list, it's going to take in the head of olink list, I'm going to stay kind of abstract here. And I just like to call it head, right. There's my nice empty function. And in terms of how I would actually want to call this function, the client would have to call print linkless. And give it like the real head of the link list, which for me in my little example here is just a reference to the a node. Cool, so I'm actually receiving the head node, which is an instance
14:41
of Node as the head of my link list here. And so let's go ahead and now set up our algorithm. So we're gonna really just implement the algorithm we just traced out on the whiteboard. So if I want to just traverse through a link less and print out every node, I'm going to need to continually update a current pointer. So I'll say current equal to the head of the link lists, which means I'm really starting at the very beginning of my link lists.
15:07
And then from there, how far do I need to go while you want to keep running this algorithm while your current pointer is not equal to no, right? Because if current is not equal to null, then there's some stuff to still iterate through. And now we get into the meat of the algorithm. If I wanted to, like print out or process my current node, I'll just console dot log here, we're going to print out this current nodes value. Right. And notice I'm writing all this logic in
15:36
terms of current, because I hope to update current properly at the end of every iteration. Right. So now that I printed out current vowel, what I want to do is update what current is pointing to. So what I should do is set current equal to current dot next. And don't be fooled here. This is a very simple variable assignment. Right? So let's run this code. And then I promise that I'll trace through how this actually operates. It's very short code, but really the foundation of most
16:04
linklist algorithms. So let's give that a run over here. I hope to print out my characters ABCD. Awesome. And there I have them. So how does this code work? Well, let's try to update and annotate this drawing as we step through the exact code here, right. So I know that in the context of my function over here, I'm really only going to track a really important variable of current. And that starts at the head of my linkless, which is passed in as the a node. So technically,
16:31
give myself some room here, I would say that the current variable starts by referencing
16:38
the A note, so I'll kind of represent like that it's aligned horizontally, right. Cool. And what I want to do now is consider my condition. So my condition is checking right? While this current variable is not equal to null, then run the code inside of the while loop. So if I check that on the first iteration of that condition is true, right, current is not equal to null. So I can run the code inside, which means I just print out the value of the current node.
17:02
Right? Since current is an instance, of node, when I do console, log current dot Val, I will be printing out the A that was initialized inside of it. So that gives me my first iteration. Now here's the important part. Right? Now, I know that current is A, so in this moment, that means current dot next would be actually referring to the B node. So if I set the current equal to current dot next, it has the effect of literally moving this over to the B note.
17:31
Now I can check my condition again, is current not equal to No, that's true. So I print out my current value of b, and then go to the next. At this point, the process just continues, right? The C note is still not equal to null. So I print it out over here and go to the next node of D. And this is still true, right? D is not equal to the null. And so I print out D. And I actually proceed another iteration, right. So right now current is D,
17:57
current dot next is null. So this would literally happen, I set my current equal to no. But things work out great here, because when I check this condition, I'm going to check is current not equal to null, in other words, is no not equal to null. And that's false. So I exit my while loop. Right. That's how I'm able to print out every node of my linked list, right ABCDE. So I think something to draw your attention to right now is how we write this condition.
18:24
I think the best way and the most robust way to write this code is to check while current is not equal to null. The most common mistake I see people make is they don't like generally that your condition should be about like roughly the tail of your link list. And so they might try to say, well, current dot next is not equal to no. Right. But that would actually cut your iteration short. If I ran that, I would only really print out ABC, right? Because when I'm at the D node,
18:56
right, I would be checking all right, before I even print out D. What's these next? Well, these next is no, so I won't even print out D, which is bad, right? So generally, when you try to write your algorithms, especially about linkless, try to write it as like present as possible, right. So I'm not going to do any premature checking of the next node, unless I really, really have to, instead, it's better to actually go to the next node, and then exit when you actually
19:23
are at the null pointer, right, the null node. So let me return this back to its former glory. And we'll just make sure that this still works is our classic implementation of a linkless traversal. It's going to be the baseline code for almost all of your linklist algorithms. Let's take this a step further. And I'll show you how you could write that same logic, but recursively it's really the same logic, you just turn it into a recursive call and a base case, right? So let's
19:48
go ahead and do this one together as well. When I promised in the next section, I'll give you a nice problem to work through. And so if I want to frame this one recursively What do I need to do? Well, I like to start with my base. case, your base case should basically be an analogy for like the condition you wrote inside of your while loop. In other words, when are you done with the algorithm?
20:09
Well, I'm done with the algorithm once. I'm looking at No, right? So I'm going to say, if head equals no, then I'm done. So just return.
20:22
Notice that here, I'm keeping this argument named as head, because I think of a link list as containing many linked lists. In other words, A is the head of this link lists. But if I look at the sub list inside B, is the head of its own linkless, as well, right and see, is the head of a smaller linkless. Still. So I think that's okay, terminology to use for a recursive function really
20:44
shows that you're buying into the recursive nature here, right? Awesome. So I'm going to stop running and just return out, once my head is looking at null. So that'd be once I'm at this point, right. But in the recursive case, what I want to do is actually process this node. So if my head is not equal to null, right now, then I'm over here, right? What I should do is just print out this nodes value, right, just like I did before, I'm just reframing current data set.
21:13
And if I want to actually progress to the next node, like I did, in my iterative solution, I just do a very proper recursive call here. So I'm going to call the same function actually makes it recursive. And what should I specify as this argument? Well, I just want to give the next node in the linked list, right, so I'm passing in head dot next. And that would be all I need to do for this one, very, very short and to the point. So let's run this recursive function,
21:40
then I'll help you trace through it a little bit more awesome. So it's working, the trace looks almost the same. But I think it's good if we do it side by side with the code over here. And really, the key argument we need to trace through is the head over here. So on our top level call, really passing in the a node as head. And so I checked my base case here is head equal to null, that's false. So I go into this console dot log, which means I print out the value a, awesome,
22:09
and now I make a recursive call upon the next node in the linked list. So if head is a, then head dot next refers to B. And since I'm making a call to that next node, in this next stack frame, head is B. And I check the condition again, is b equal to no, that's false. So I just print out b over here, and then make another recursive call on B's next, which is C, right? And this process continues,
22:35
all the way down to let's say, a when head is D, right? I check this condition is d equal to no, that's false. So I go ahead and print out D, which is like the last logical node in my linked list. And I would make another recursive call upon DS next, right? So of head is D, head next is no. And I would indeed make this call. And now I'm back inside of this new call, and I check his head equal to null. And that's definitely true right now. So I return, that's my base case.
23:07
And I end my recursion, right, this base case, is really, really important. So I want you to compare and contrast, these two pieces of code, they really implement the same algorithm. And as we go through these linkless problems, sometimes I'll show you both ways to solve it. depending on you know, what style of problem you're solving, you might find the recursive or the iterative, a little easier to write over the other, which is why I think it's important to practice both, but
23:30
maybe, you know, choose a favorite and decide what you're most comfortable with. But that being said, practice both. Alright, let's head back into the whiteboard. Hey, programmers, Alvin here, right. And I want to go over a approach for this link list values problem. So hop right in right here, this problem is going to be given the head node of a linked list we want to do is return an array
23:50
containing all of the values within the nodes of that linked list, we should do it in order. Bear in mind in this problem, we're given a Singly Linked List, which means that every node has a pointer to the next node in the linked list, we know that the last node of the linked list would have a next pointer that points to know that being said, how do we go about solving this one? Well, there's problems, we're just going to have to force you to implement a really core linkless
24:14
pattern that is just traversing through a linked list in order. And so we'll start by attacking this one, maybe with an iterative description. So let's say we started from ground zero, right? So we want to create our values array, and to the side, we can just initialize values to be an empty collection. And to implement this core pattern of just traversing through a linked list, we're going to need a variable or just a pointer. And we're going to start at the head
24:38
of the linked list, right? Bear in mind that our function only takes in the head, but I know the head is like the ultimate starting point of the linked list. And eventually I could access everything throughout the entire list. So I'm going to set my current equal to the head. And what I can do off the bat is just check current value and add it to my running collection. So I have the a value inside of values now And since I have access to the current node, I know
25:02
that if I access its next property, I would have access to the next node of B. So what I can do is set current equal to current dot next, basically just moving my pointer to the next node like this. Same thing as before I can add my current value into the collection, I'll just proceed in this way, right, same thing for C, set current equal to current next.
25:25
And things get interesting once we approach the tail of this linkless. So I'm currently at the D node. And I go ahead and add that value into my values list. Well, we'll have to do now is consider the scenario when it's appropriate to actually stop our traversal. Well, bear in mind that these next actually points to know. So maybe I'll draw that explicitly just for this drawing. So these next is just pointing to null. Which means if I
25:48
continue this algorithm in the general sense, so I set current equal to current next, that means my current pointer now points to know. And I think that would be a perfect stopping condition. Right? So once current is no, we know that we've hit the end of our link list. And so we're totally done. And if you look at the order of our values, it is indeed the correct order, right? What can we say about the complexity of this algorithm? Well, if we say that n is just the
26:11
number of nodes in this link lists, then the time complexity is going to be O of n, right? Because we're just are really iterating through every node once. And our space complexity, if we consider the output right now would just be also linear in the number of nodes over here. And I'll tell you what this looks like a pretty good strategy, we can go ahead and implement well implemented in two ways. First, I'll show you the iterative version, and also show you how
26:35
to implement this one recursively. Really, both the iterative and the recursive code use the same sort of mechanisms. So I'll see you in the walkthrough video.
26:45
Hey, programmers, Alan here, right now want to go over a JavaScript solution for this linklist values problem. So we'll jump right in. And we'll start by implementing, I think, the iterative version that we spoke about in the approach video. So if you haven't watched the approach video, definitely make sure you check that out first, right. And so I'll get the ball rolling over here, what I want to do is use a pointer really just a variable for me, right, so I'll say let current,
27:09
I'm going to initialize it to be the head. And I know that though, most important pattern I probably need for a linked list is just a traverse in order through a linked list. And the way that looks is I want to keep iterating while my current is not equal to null, right, so just not equal to null, no would mean the very, very end of my linked list. Nice and very standard code I need inside is to progress to the next node of the linked list. So I said current
27:37
equal to current dot next. So now think about actually generating the return type. For this function, I do want to return an array of all the values. So I should initialize that up top, I'll say let's, or maybe const values, because an empty array. And then as I actually iterate through all of my nodes of the linked lists, at the tippy top of this while loop, I can just take my current
28:01
nodes value, right, every node has a dot Val and also dot next I'll take the current nodes value, and just push it into values, right? So values dot push, that single Val. And once this while loop is done running, I must have hit the end of the linked list. So I can just returned the complete values array. So before we run it, one thing I want to always emphasize is for your link list,
28:26
a main logic, it's always important that you try to write your logic about just your current node. So for example, my condition is saying, while current is not equal to null, it doesn't say like while current dot next is not equal to no, right, you can probably get away with finessing code like that, but ends up being more clunky than anything. In other words, whenever I try to write my logic
28:50
for linked lists, I always try to stay very present, right, so just worry about your current node. So what I don't like to see is patterns like this write current dot next dot Val, and try to just shift your frame of reference because if you do that, then you're actually kind of assuming that your linkless has a particular length. So instead, I always try to write all of my expressions about simply current, right, so while current is not equal to null, then I
29:14
push current dot Val. And then I can just update current to be current next. And I can be assured that every node is going to be processed in this algorithm. So let's give this a test run now.
29:27
And if all is well, we can transition into the recursive version now. Awesome. So how can we do this recursively I'll just do that down below. So the way I would structure this one, just so I get the most optimal complexity is really with two functions. So my main function will do almost the same thing. It is going to call a helper function. I'll call this helper function, maybe fill values.
29:51
And this function is going to actually do the recursion. So it's going to take in the head of the linkless, and also a reference to the values array. So recall that in JavaScript if I pass any non primitive types, so basically, things like arrays and objects, they are going to be passed by reference, right? So what I want this fill values function to do is to actually mutate the values array, because this main function is going to return it. So what does that recursive function
30:16
look like? So we'll say fill values, it's going to take in the head, and also the values, right? I'll start with a base case here. And really, what we're trying to do is just translate the same patterns from the iterative code just into their recursive variations, right? And so I know I need to stop my recursion, once my head is no, right. So I'm going to check if head is equal to null,
30:42
then you can stop. So just simply return, right really important distinction here is, you're going to have a tough time and probably end up with some clunky code, if you say, if head dot next is null, right. So again, I always try to stay very present, and all of my code, so don't worry about your next node, just handle yourself, right? Eventually, every node will get served here. So if head is null, then nothing much to do just return and you can stop your recursion. Otherwise,
31:09
I know that head is not null, so it must be a node, I need to take that nodes value and add it to values, right. So I can say, head dot Val, and I want to push that into the values collection, right, we're call that values is referring to this outer array here. But beyond that, besides this current head, there could be other nodes right in the remainder of the linkless. So I can just call recursively fill values, and instead of pass along head again, I need to
31:38
pass along head dot next, right. And that means in that recursive call and kind of jump back around, and now head is referring to the next node, and so on, and then its value is going to be added all the way until we get to the very, very last node. Technically, after D, we would hop to these next, which is no, in which case, we would exit due to this base case, exactly. And before we run it, just a few issues that I need to fix, I see that missing an equal sign here.
32:06
And also when I call filled values, of course, you need to pass along the same values array, because I know that every call wants to add its value into the same values array there. So we'll give this a test run. See what we get. Cool. And now you also know how to implement this algorithm recursively. So the reason I like to split up my recursive version for this algorithm into two functions
32:31
is so my recursion doesn't actually have to create like multiple arrays, right? Instead, all of these recursive calls are just adding their values to a single array. If I actually created like copies of arrays all the way through the recursion, I would end up with like an n squared, sort of runtime. Cool. So when it comes to comparing these two implementations, they're actually equivalent
32:57
terms of their time and space complexity, right? All right, programmers. That's all I got for this JavaScript walkthrough. I want you to practice both the iterative and recursive versions, because they're gonna both be very useful for the next upcoming problems. I'll see you there.
33:13
Hey, very amorous. Welcome back. Right. Now I want to go over an approach we can use for this some list problem. So in this problem, we're going to be given a singly linked list containing numbers as the values, what you want to do is return the total sum of all the values in the linked list. So for this particular input, we should return a total sum of 20. And so how can we go about solving this really just reviewing a core linked list pattern, right,
33:35
all you have to do here is just traverse in order through the link list, and you can accumulate a sum. So let's say we start from the beginning. If we initialize some some variable to zero, we can also just use a pointer that starts at the head of our linkless. And what we can do is we can take current value and add it into our sum just updating the sum. So I take my current value of to add it to my sum, by total sum is right now to that I can set current equal to current next,
34:03
I can add this eight into my sum getting 10. next iteration, I can add my three into the sum getting 13. next iteration, I can add seven into the some getting 20. Alright, and I know that technically seven does have a next pointer, and it does point to null. So let's say I do that out explicitly. What I can do at this point is actually continue my algorithm. And I can make the stopping condition when my current points to null, right. So in general, we can call this up by saying a
34:30
loop like, you know, while current is not, no, we talked about the complexity of this algorithm, it's pretty straightforward. We're definitely just iterating through every node. So if n is a number of nodes, we have O of n time, roughly one iteration of for every node, and then our space complexity here is actually o of one if we do this iteratively, right. The only variables we need to maintain are really just current and also the sum variable and we're just
34:53
going to store some primitive values in there. So we have a nice constant space solution over here. So the internet It was really straightforward. Just for, you know, complete understanding how can we solve this one recursively. If you saw that recursively, that means you have to, you know, call your function many times, and we start with a top level call on the head node of two.
35:13
And what this should do is really just call upon the next node, right? So I could call upon head dot next session, give me a call to this eight node, and that should call upon the three node, and that should call upon the seven node. And finally, the seven node should actually call upon its next, which would be the null node. And that will actually act as my base case, I think it's a really great one, where I can do with this base case, right? If my node is null,
35:39
then I can just return zero, right? Think of no as if it's an empty linkless. What is the total sum of an empty list? Well, that would definitely be zero. So I'm going to plug in this return value, right? So I'm saying this call to the null node is going to return zero. When we say return, that means returned to your caller. So the zero would actually be returned into the seven node, what
36:03
the seven node should do is at its current value, write its own value into that number, giving seven and then that returns up the stack. At this point, I returned back to the three node three can add its value with that seven getting 10 Just returning that up, eight can do the same giving me 18. And finally, two can add itself into that return value giving us 20. And that would be the
36:26
correct answer, right. So there are plenty of ways to implement this one. If we solve it recursively, we're definitely going to have one call for every node within our linked list. So that'd be O of n time. And the space complexity would actually be a little more than our iterative, we would have O of n space here because of the call stack. Right? Typically, when we analyze our recursive functions, we should include the space utilize for making these recursive function calls,
36:50
right? So O of n over here. And notice that when we bought them out at our base case, we would have you know, roughly like four or five things on the call stack. Alright, so those are the two strategies, I'll think well code up, and I'll catch you in the walkthrough video.
37:06
Hey, programmers, Alvin here, right, now I want to go over a JavaScript solution for this sum list problem. So I think we'll get things kicked off by implementing a iterative version for this. So I know I want to create a sum and add to it over time. So I'll create that variable, I'll say, Let's sum equals zero, I know by the end of this function, I'm just going to return that total sum. Now I need to lay down my very standard code for just traversing through a linked
37:33
list. So I'll say let current, we're going to keep updating this variable over time. And it's going to initialize with simply the head node. And I know that in the loop for this kind of classic linkless traversal, I just want to iterate a while current is not equal to null, right? If it's not equal to null, then it's a node so I can actually look to its next pointer. So I'm going to need
37:58
this pattern, right set current equal to current dot next, this actually steps through, you know, the link list and sequence. But how do I actually want to utilize my current nodes value? Well, I just want to take it and add it into the sum, right? So sum plus equals current dot Val. And eventually, once I hit the very, very end of the linkless, I know current is going to be equal to null. So I exit the while loop. Now just return my total sum. So let's run this. Just a little
38:26
variation off of our last problem, just doing some computation along the way. Nice. And now I think I'll show you the recursive version, which I quite like. So for your recursive version, it's all about starting with a meaningful base case, right? So first thing you think about is alright, typically, for my linkless problems, my base case is about my head being null, right? And that kind of represents the scenario where my linked list is an empty linked list, right? If it's null,
38:54
that means it has no nodes. So what's the total sum of an empty linked lists while it's just zero, so I'll check if head is equal to null, then just return zero? It's important I think about compatible types here, I know, when my linked list actually contains some nodes, then I should return a number. And even in the base case, I should return a number. It's just the case that I return the number zero. Nice. Let's say now we write a recursive code, right? If the head is not
39:22
no, then it's actually a node. So I can look at its value, right? Because the head dot Val, what I want to do is take that number and add it to the sum of the remaining nodes in the linkless. How can I get the sum of the remaining nodes after my current position? Well, that's just about calling your function recursively. Right? And passing along head dot next, right? So always try to think about your recursive call for the type of data that it returns, right? It gives me back
39:48
a number representing the total sum of everything starting at the next node. I'll take that number, add it to my value, and that should give me my complete sum. So I'll just return it So I'll give this a shot. And the recursive code is quite short. One thing we should consider though, when it comes to like an apples to apples comparison between the recursive and the iterative, um, they both have the same runtime, right, they both have O of n. In the case of my recursion, I have
40:17
N calls in the case of my iterative code I have and just iterations in the while loop. But the recursive version also uses n space, right? That's because for recursion, we actually have to add every function call onto the call stack. So I know by the time that my recursion bottoms out a base case, I would have n calls on the call stack. Whereas in the case of our iterative code, we would actually use only a constant amount of space because we only use a handful of variables
40:46
here. That being said, I highly recommend that you practice both of these solutions, because depending on the problems that we solve, you may find a one more natural to use than the other, hey, programmers, before we continue the course on linkless, I just want to make you all aware of my own data structure and algorithm platform that is struck the dotnet. If you haven't noticed already,
41:05
all of the content that you're launching in this course, as well as some of my other material on Free Code Camp is also on structure dotnet, with a lot of other topics covered as well. So we go into the course, I cover all of those classic, you know, data structure algorithm topics with tons of videos for every single one. So if you like my teaching style, I think you'll also enjoy structure dotnet. And if you hop into any particular problem, I'll give you a quick little
41:30
tour over here. So if we go to this insert, no problem. Like you expect, you can write your code, you can view the problem, you can run your code, see the output, I think most importantly, what will bring you the most value is my kind of signature videos, right. So you're going to be able to have a high level approach for every single problem as well as the code walkthrough. So you get the nuts and bolts code implementation for every single problem. And even
41:55
still, if you're not like a JavaScript, I know that this free coke and video is in JavaScript, you can totally switch the language. So for all of my C++ people in the crowd, doing so is that is switching to C++ would obviously change the prompt in the text editor. But also, you'd get different videos right here you see a C++ specific video over here, right. So if you've been enjoying my content, and just want to check out more data structure and algorithm material with me,
42:20
head over to structed dotnet. I'll leave a link to the platform in the YouTube video description. And with that, let's head back into our linkless course. Hey, programmers, welcome back right now I want to go over the approach we can use for this link list find problem, and I'll show you two ways to solve this one. So in this problem, we're going to be taking in a linked list as input. And we
42:41
also have a target value we want to do is return true or false whether or not the target value is contained within the link list. So for this particular example, I'm asking for a target of C, you should return true because C is definitely within the link lists. In another scenario, let's say I gave you a target of G. And that's an error, you would just return false because g is not a value of this linkless. To solve this one, we're just going to use our classic
43:07
linkless traversal algorithm. So we'll step through it as if we're looking for C. So in the long run, we expect to get back a true here. Well, I know that they're going to give me the head of the linked list as input, and I'll create a current variable that points to the head node, of course, I'm going to progressively update this current variable to be the next node over time, right? So what I can do is whenever I'm situated at some current node, I can check if my current
43:31
value is equal to my target value. So right now I would check is a equal to see it's not. And so I should keep looking through the link lists. I know that current also has a next property. So I'll update current to be current dot next, and then I check is b equal to C? It's not. So I keep going. And finding that can hit a point where I see that my current value of c is equal to my target value
43:54
of c. And so I can just do an early return true, right? Once I find a match within my linked lists, I can just return my final answer. Now let's say we had the opposite scenario, let's say that my target was G, we're going to start the algorithm and the same way we start at current. And we keep looking through the linked list. And we set current equal to current next, eventually, we know that current is going to be equal to null, which sort of signifies that we've hit the very
44:20
end of our link lists, right. And at this point, once we finish iterating through the entire linked list, we know that we didn't see the target value because we were checking the entire way through. And so at this point, we can do return false. This is a really practical programming pattern, right? Where we check some conditional inside of a loop. And if we find something we're looking for,
44:38
we'll return true early. And afterwards, after our loops done running while return false late. We talked about this iterative strategy, we know that if n is the number of nodes, we're just going to iterate through every node of the linked list, so we would have a runtime of O of n. And our space complexity here would just be O of one because we're just using a constant number of variables. So That was the iterative solution, how can you also solve this one recursively.
45:04
So let's say we were looking for the target of C, and we had a more recursive point of view. So we know we're going to make a top level call on the head node of our linked lists. And I can just think about some base cases to use here, right? And I know I need two base cases, right? One that can return true, and another that can return false. So for my first base case, I can just simply check, alright, if my heads value is equal to my target, then just return true.
45:29
And the opposite scenario, let's say that my head is no, then I should just return false. What I always try to do with my recursive code is the thing about my base cases as if they're their own valid inputs. So in particular, for base case number two, if head is null, then that kind of represents the empty linkless. If my linked list is empty, then I can return false because I definitely can't find the target within an empty linked lists. So how would this
45:55
run for current input of targets C? Well, I would check, alright, is a my target it's not. So I make a recursive call upon B. Same thing, right? It's not make another call upon C. And at this point, I see that my current heads value is equal to my target. And so this node is going to return the Boolean true. And I know that this return value is going to return back to its caller of B. And then
46:18
B is going to pass it back up to a and of course, a returns it to the very, very top level call.
46:25
Let's say we had a scenario where a target was not found within the linked list like G, then we can see the other base case fire at the very end, right, so I'm going to make a call on a, a calls B, B, call C, I still find the value c calls D. And finally, when D looks at its next it's going to pass along Nol right, because these next is technically no. And at this point, I just hit base case number two,
46:50
so I can return false. And like before I return these values up the call stack.
46:59
When we talk about the complexity of this recursive algorithm, we can say that n is the number of nodes, we're definitely going to have O of n runtime, because we make a call for every node of the link lists. But we also have O of n space, right? Because each of those calls by the time we bought them out at a base case, we would have to store those on the call stack. We know that the worst case scenario is if our target is not found within the link lists.
47:25
That being said, I think these are two fair algorithms to go ahead and implement. So give it a shot on your own. If you get stuck. I'll catch you in the walkthrough videos. See you there.
47:34
Hey, programmers, Alvin here, right now I want to go over a JavaScript solution for this linkless find problem. So we'll jump right in. And I'll start by showing you all the iterative solution. And so we'll start with our pointer variable, we'll say let current equal the head. And we'll just lay down the foundation, right? We know we always need to iterate, while current is not equal to no. And while it's not know, if we want to progress to the next node
48:00
of the link lists, just set current equal to current dot next. Now I just need to work in the logic specific to this problem, right. As I check every current node, I want to see if its value, so if current dot Val, if that is equal to my target. And if it's equal to my target, then I can just return true cuz I found the thing I'm looking for. What I want to do is return false only after the while loop, right? It's important that I return false after the while loop.
48:28
Because only after you check every single node of the linked lists, can you actually confirm that, hey, the target value is not within the link lists, what you don't want to do is write a like if return true, and then else return false, right, this code would be wrong. Because let's say you don't find the target value in the very first note of the linked list, then you would just incorrectly return false without even looking at the rest of the linkless.
48:56
So none of that we at least want your code like this. So let's give it a test run, see what we get. Nice. And there we have our iterative solution for this linkless find problem. Let me quickly show you the recursive version of this, it's going to be very similar. So in the approach video, if you haven't watched the approach video recommend you do. But in the approach video, we mentioned that we can solve this recursively by just using
49:19
two base cases, right? I'll start with the base case if my head is equal to null, all right, so that kind of represents the end of my linkless or also just the empty link lists. So if head is no, I can't possibly find the target within an empty link list. So just return false.
49:36
Now I need my other base case, right? paid my like affirmative base case. So if head is not know that I can look inside of head and I can check if head dot val is equal to my target, and I've just found the thing I'm looking for so just return true. So two base cases here, right? One affirmative and then one that returns false. But let's say neither of these are true, right? So my head is not no
49:58
and my head value is not equal to my target, well, then I need to check the rest of the link list. So here's where I bring in recursion. And I check the next note. So linkless fine of head dot next, and you can pass along the same exact target. So this is going to tell me, alright is the target found in the next notable and glass or in the remainder of the link lists. And I know that this call is going to return a boolean piece of data, right,
50:24
either true or false. I just want to pass that up. So this should be good to go pretty concise code, give that a shot. Cool. And there we have a solution that's recursive. For this problem. Do you bear in mind when it comes to the comparison of the complexities? Technically, we would prefer the iterative version, right? They both have linear time. But the iterative version has constant space, right? I'm just using like a current variable.
50:52
Whereas my recursive code uses a linear amount of space because of the call stack. That being said, what I want you to do is practice both of these solutions. And I'll catch you in the next problem.
51:03
Hey, programmers, Alan here, right? Now I want to go over the approach we can use for this get node value problem. So in this problem, we're going to take in a linkless. And what we want to do is also accept an index as input, what we want to do is really return the nodes value at that given index, and we will start counting our indices at zero. In other words, we'll consider the head of our
51:24
linked list as having index zero. So for this particular example, if I asked you for index two of this linked list, you should return the value of the C note right? So just return the value c. And of course, that could be giving you any particular index as input. So what this question asks is pretty straightforward. But how can we go about solving this one. And so what we can do here is a basic counting algorithm. So we know we want to return the nodes value, who has index to,
51:52
so when we initialize our current pointer to be the head of the linked list, we'll initialize our count to zero, then from here, it's just our classic logic, right? I know I can set current equal to current dot next. And when I do that, I'll also increments might count. So now count is one. Basically, I have tracked the index of my current node that I'm iterating through next iteration when current goes to see, and of course, I increment my count to two.
52:18
At this point, I can see that my target index and my count are equal. And so I can just return the value within that particular node. But think about the strategy. It's pretty straightforward in that if n is the number of nodes, the time complexity is simply O of n, right? Because in the worst case, we just have to traverse through the entire linked lists. We can also say that the space complexity for this is constant, because we're just tracking some simple number variables.
52:42
So that's how you can solve this one irritably. How can you also think of this one recursively, though, so let's reframe our point of view here, let's say that we were forced to solve this one recursively. And we know we still want to find the value at index two. And when I make a call, I know that the top level caller is going to pass along the head of the linked list, so the a node,
53:01
and also their target index of two, I can use my classic recursive linkless traversal algorithm. So I make a recursive call on my next node. When I make the recursive call on the next node, what I should also do is pass along the index, but decrease it by one. So now I'm able to see that, hey, this current note of B has index one. And if I keep doing this next iteration, I call upon my next note of C, and I also decrement, my index down to zero. Once my index is at zero, that
53:31
basically means that I want to return this very node, right. So if index is equals zero, we'll return no dot value, that would be our base case. And once we return that value, I know that I'm going to return back up the stack. So the c value returns to its color, and so on and so forth.
53:49
Very classic recursive code. So this looks like a nice recursive algorithm, we analyze the complexity of this, we're going to see that the time complexity is still in here. And the space complexity is actually also linear here, here, we incur a lot more space complexity, because we're going to be storing every call upon the call stack. So what I want you to do is on your own, try to give it a shot, implement both the recursive and iterative solutions
54:13
for this problem. And if you get stuck, I'll catch you in the walkthrough videos.
54:19
Hey, programmers, welcome back. Right now I want to go over a JavaScript solution you can use for this get node value problem. So hopefully, you already watched the approach video, if not highly recommend you do that. And we'll start by implementing maybe that recursive strategy off the bat. So I'm going to need two base cases here, like we said in the approach, and one of them typically is always going to be if our head is equal to null, that means I've hit
54:44
the end of my linked list or I have an empty linkless. And what I should do is just return know that we'll actually cover a few scenarios. If I look at the examples here. Sometimes we may actually get past a very, very large and Next. So notice here, they're asking for the value at index seven. But the link list only has four different nodes, that means the index of the last node D would be three, right? 0123. So if ever our target index is out of range, then we should just return
55:17
null. And so this should help me satisfy that, because I'm going to return no, once I fall off the edge of the link list. Nice. We're gonna need another base case, what if we actually find the particular node that we need to return its value for. So in over time, I'm going to decrement my index like we set in the approach. So I can check if my index is equal to zero, then simply return this current node, the current node would be head, dot Val, right, returning its value.
55:48
Nice. So bear in mind, we're counting down here. So in my recursive code, I need to call my function, get node value, pass along the next node of the link lists, and then pass along index minus one. And I know that this call is going to return the value of the node at the given index. So I should just return whatever that comes back. As
56:11
I do a quick sanity check here. Bear in mind, we're counting downwards. So for like this example, example, 00, we know that A is going to have an index of two, right technically, because we're going downward. And when I make the call for B, it's going to receive index one, when I call on C, C is going to receive index zero, which means I should just returned that back up the stack. So kind of counting downwards here in the reverse. But this should be a nice solution.
56:38
Let's give us a test run. Bear in mind, this solution has a linear time complexity and also a linear space complexity, we can actually cut down on the space if we write the iterative version. So I'll show you that right now. So the intro translation, you should be very familiar with probably wondering, why are we doing such simple problems? Well, it's about to get more difficult, right? To me, it's all about the foundations. So our classic strategy is for iterations, set
57:05
your current variable to be the head node, right, I'll just lay out the classic traversal. So while my current is not equal to no, then keep on going to progress to the next node in the sequence, what I should do is set current equal to current dot next. And now I need to work in the problem specific logic here, right? I know I want to return the node at the given index. And for these iterative patterns, all counts upwards. So I'll set some count variable equal to zero,
57:35
just like this. And whenever I progress to the next node of the linkless, all set count plus equals one. So I'm counting upward. So when I get to some point when my count is equal to my target index, and I can just return this node, right, so I can return this nodes value. So again, we're counting upward in the air diversion, whereas in the recursive version, be counted downward. Nice. Let's go ahead and run this code. There was one thing that probably won't
58:09
pass, but we'll give it a go. See what happens. So I'm getting an error here, get node value has already been declared, because of course, I have it defined twice. So we'll try that again, can't read declare your const variables. So we'll run it. And we're failing test 02, which is the test where our index or a target index is too large. So here's 02. So we should have our function return null. If we can't find the node at the specified index,
58:38
right now we're returning undefined, which is happening because this while loop is actually ending, right, we're going to hit the very, very tail of our link lists. And so our while loops over and we're just going to hit line 16. When we fall off the edge of our function evaluation, we're just going to by default, return undefined. So to fix this, it's quite straightforward, just by default, return null. And that should satisfy that scenario. Let's give it a run there.
59:07
Cool. And there, we have an iterative solution. So for this iterative solution, it has a linear time complexity, just like the recursion, but it has a better space complexity right here, we consider this constant space, because we only use a handful of variables, like current and count. That being said, what I want you to do is practice both of these implementations, because in the next few problems, it's going to get a little more involved. I'll see you there.
59:35
Hey, programmers, welcome back. Right now let's go over an approach we can use for this reverse list problem. So in this problem, we're going to take in a linked list that's input. What we want to do here is actually reverse the order of the nodes in this link lists. So if our input list contains the values ABCD in place, meaning we want to mutate the existing linked list in place, we want to actually change the order to DC ba just ending up with the link list. in reverse order.
1:00:02
In this function, what we should do is also return the new head of the linked list. So technically, your function for this input should return the D node. So let's come up with a strategy we can use to solve this one. When it comes to the tools we can use for a linked list, we know more or less, we always have to iterate or traverse through the entire link lists. And we know that that requires at least one pointer. Typically, we call it current. The trick here is actually use
1:00:27
multiple variables. So let's say I began my classic current pointer pointing at the head of the link lists. What I'll also need is to track the previous node I visited at the start, because I haven't visited any other nodes, we can make this previous pointer point to know.
1:00:45
And we know this entire time, if I have access to current, I also have access to the next node in the list right by just accessing current dot next, we're just going to label that as a temporary variable here. And we'll call it next. And you'll see why in a little bit. So I know I need to have the long term effect of just reversing all of the next pointers in this link list. In other words, I need to make a point to know. And so what I can do is literally just
1:01:11
set current dot next, in other words, setting the arrow to point to previous ending up with this. Now it should be abundantly clear why we saved the B node with that next variable, because once we reroute current dot next to point to No, we would lose access if we didn't have that next variable. So what I can do now is shift my point of view, I can set my current to be the next and set my previous to be the old current just shifting my point of view,
1:01:38
like this. And now I can set current dot next to be the previous node once again, rerouting this pointer. And this process continues. As we get toward the end of the link list, we have to also remember is technically since D is the old tail of the linkless. This entire time, it actually did have a next pointer just happened to point to know.
1:01:59
And so at this point, I can actually continue my general algorithm right, I still set current dot next to my previous rerouting this pointer. And I can actually continue one more iteration. If I set current to be the next, it's now the case that current is actually at null, which means we hit the end of our linked list and we can stop our algorithm. If we look at the current state of our linked lists, it is in reverse order, right D points to see
1:02:25
points to B points to a points to null. So things are good to go there. And if I wanted to return the new head of the link lists, I can simply return the final value of the previous variable. So that actually works out pretty elegant. If we do the analysis for this algorithm, if we implement this in an iterative way, and we say n is the number of nodes, we know that the runtime is just going to be O of n, really just traversing through the entire linked list once
1:02:51
we can say that the space complexity is constant, because we only need a fixed number of variables. So overall, this is a maximum efficient algorithm to reverse a linked list. When we go on to the code walkthrough for this, I'll actually show you how to implement this iteratively and recursively. Bearing in mind that the recursive would actually suffer a slightly worse space complexity. But before we get there, try to give this a shot on your own implement this if you get stuck,
1:03:14
I'll catch you in the walkthrough video. See you there. Hey, programmers, welcome back. Right now I want to go over a JavaScript solution we can use for this reverse list problem. So hopefully already watched the approach video, if not, I highly recommend it, because we're gonna implement that strategy pretty closely. So I'll start with the iterative version here. And we know we just need to lay down at least initially, our classic linkless traversal is just going to
1:03:38
keep my current variable initialize that to head and loop while my current is not equal to no. And I know that the basic code would always be set current equal to current dot next, that would just move sequentially through the linked lists. But we need to work in a few other variables, right. So the key here is to have some variable, we'll call it previous and to initialize it equal to
1:04:02
null. And if we were wondering why null is a great default value for this previous, just think about what needs to happen on the very, very first iteration of our while loop. So we know that our current is going to be a, and in the long run, we know A's next needs to actually point to No, right because he needs to become the tail. So if we initialize previous with no, on the first iteration, we can immediately just say current dot next, equals previous right,
1:04:29
that would actually have that arrow point to null, which is good to go.
1:04:34
But then at this point, we need to make sure that we have some proper references here. So before we just reassign current dot next, if we just overrode it, willy nilly, then we would lose access to whatever the actual next note sequentially was. So I'll save that to a variable. I'll say maybe const next, equals current dot next, and then after I override it, I can still make progress to the next node of the linked lists. by simply setting current equal to next,
1:05:03
awesome. So that's looking pretty good. And not only do I need to progress current, but previous should now also point to current shifting my full point of view. So some pretty tricky logic over here. Let's go ahead and maybe analyze a little bit closer, what it's doing, please mask er here. So let's say we had a link list that looked like this A points to B points to see, we know we have initially current over here, right, so current is pointing to a,
1:05:36
we know that when I save that next variable, it's going to point to this B over here. So I'll save that. And technically at the very start, we initialize previous to be null. So I'll just use like capital n represent null. And I know previous is going to point to that like this.
1:05:52
Awesome. So on the first iteration, we have all these variable setup and I set current dot next equal to previous current dot next is represented by this arrow. So when I say current dot next to be previous, it has this visual representation, right, just setting it the opposite direction, once I do, they would actually lose this arrow. And now you can probably see why we saved next for B, right, that way, you don't lose access to the rest of the link list.
1:06:22
Cool. At this point, I can set some variables, right, I can make previous, the current, so I'll set it like this, then I also set current to the next. So basically just shift over the point of view. And if you look at the state of my drawing, now, things are actually perfectly aligned. For the next iteration, I would just set current next to be previous once again, and so on and so forth all the way through the very end of the link list. And like we said in the approach,
1:06:51
once we actually end when current is equal to null, you exit the while loop, and previous would actually contain the new head of the link list. So I'm just going to return previous over here, it doesn't make sense that previous would be the new head of the link list. Because after exit the while loop, I know previous is going to be the original tail, right? If I'm reversing the tail becomes a head, and vice versa. Cool. So really just a spin off of our classic linkless traversal,
1:07:18
I will tell you that the logic here can get pretty tricky, especially with these temporary variables. So we'll give it a test run, see what we get. And hopefully, we'll have this nice O of n runtime o of one space solution. Awesome. There we have it. And so what I'll also do now is show you the recursive version, it will have a slightly worse space complexity, although the code is noticeably more concise. So I think it's still worth practicing. So really, we're just going
1:07:45
to translate the same premise into its recursive version, right. So I'm going to still need like access to two variables, or two pointers. And the way I establish that recursively is by using a default argument here. So I'll set previous equal to null. So if you're unfamiliar in JavaScript, this is how you just do a default argument. Right. So if someone does not pass in a second argument, when they call reverse list, by default, it's going to be set to null. And I can
1:08:11
start with the classic base case, right? If head is null, then I've hit the end of my linked list. And what I can do is actually just returned previous for the same reason I returned previous over here, right previous would actually be the new tail. And when it comes to actually writing the recursive code, I'm just going to try my best to translate all of these iterative patterns into their recursive analogues. So I'm going to save a reference to the head next,
1:08:37
just a temporary variable. Because if I override it by saying head dot next equals previous, I would lose access to it otherwise. So now I at least have a way to call recursively and traverse through the rest of the link list. So passing next, as the new head and pass in head as the new previous, really just shifting that point of view, once again,
1:09:01
I think about the return value for verse list, I know it's going to return a node, right, it's going to return hopefully, the new head of the linkless. So I just want to pass up that return value, do stay aware in this problem, they say your function should return the new head of the reverse link list. And this should actually satisfy that. So we'll give this a run.
1:09:24
Nice. And here we have a O of n time recursive solution that is also O of n space, right? So apples to apples comparison, if you want it to get the most efficiency, you should prefer the iterative version. That being said, I still think there's a nice value to practicing both of these. And this is actually a pretty common interview problem. So make sure you have this down pat. Before we hop into the next problem. I'll see you there.
1:09:50
Hey programmers, Alvin here, right now I want to go over the approach we can use for the Zipperless problem. So in this problem, we're going to take in two linkless, whatever Want to do is zipper these two lists together. In other words, I need to in place, reassign all of these next pointers such that we alternate between the nodes of list one and list two. And also looks like we should
1:10:11
always start with the first note of list one. And then from that point on simply alternate. That being said, let's take a look at another example. We don't have many assumptions we can use when it comes to the length of both of our lists, except that we know that each list is actually non empty. But besides that, what if one of my lists was longer than the other? Well, then what I want to do is alternate as much as I can, and then just terminate the link lists with the remaining
1:10:38
nodes. Soon as I alternate with AQ br, at which point I don't have any more nodes in the list too. So I just take all of the remaining nodes of list one and add them to the very end. And so we'll want to keep that edge case in mind when we come up with a strategy for this one. So where do we even start with a problem like this? Well, you should be familiar with our core linkless pattern, right? We just know how to traverse sequentially through a link lists.
1:11:03
And so what I can do is actually maintain two pointers at a time right? One for list one and another for list two. So let's say we started stepping through this example. I know I'm past both of these head nodes, head one and head two respectively. And then from there, I can set up some respective current pointers. And so given in the examples, we always want to start with the head node of list one. So I'm just going to start that down here. And what I'll
1:11:30
need to do is also track the tail of my output list, right? Although we're just reassigning all of our pointers in place, we're going to need a reference. That way, we can figure out how we can add new nodes to our current output, we'll say. And since I already begin my chain with the first node of list one, then I need to be sure that I actually progress current one. And so current one should really be pointing at this B node. And so now that I have
1:11:59
at least a starting node, how can I come up with a general algorithm here? Well, if you want to establish a simple alternating pattern, then what you can do is just use a counter variable haven't started zero. And then based on whether or not the count is even or odd, that would tell you from which list you should take your next node. And so since I already began with a node from list one,
1:12:20
what I should do is whenever my count is even, I'm going to grab a node from lists to when count is odd, I'm going to grab a node from list one. So right now count is 00 is technically an even number. And so I'm going to take my next node from list two. So I look at my current two pointer, and it tells me I should just take that cue node and add it as the next of my tail. And so now that I've consumed a node from list two, I need to be sure I progress current to to its next,
1:12:50
just like this. And I also need to make progress on some other pointers here, I need to progress my tail also to its next, that way, I can get set up for the next iteration of the algorithm. At this point, I need to increment my count by one. So now count is one. Since my count is odd, I should take a node from list one. So I look at my current one pointer, and I add b to the tail, just like this. And I make progress on all of my variables, right. So I'm going to progress
1:13:18
current one, I'm going to progress my tail and increment my count to two. Since it's even now I should take a note from list two. So I take my AR from current two. And when I set current two to its next, it's going to become No, when I set tail to its next, it's going to be set to the r, and then I increment my count. So now my count is three. And now I have an important scenario, it looks like I've exhausted all of the nodes in list two, we spoke about this scenario,
1:13:48
right? Whenever we finish all of the nodes of one of our lists, we should just terminate our output with all the remaining nodes of our other list the non empty list. And so at this point, what I can do is just take my current one, basically this C chain and everything after it, and just put it after the tail in my output,
1:14:10
just like this. And of course, I want to complete the connection over here. And this would actually be the correct output. And so overall strategy was to maintain pointers to both of our respective link lists, and maintain accounts, right, depending on whether the count is even or odd, then that'll tell me from which list I should take my next node. And along with that, we also need to maintain some tail pointer we can use. So we can actually build up the linked list output.
1:14:37
Let's talk about the complexity of this one. Since we have two linked lists as input to this problem, we should probably use two terms to describe its complexity. So if I say n is the length of list one, and I say m is the length of list two that I can say the time complexity is the minimum between n and m. Recall that when we just step through this algorithm, we really only needed as many iterations as the shorter linkless. Recall the algorithm we just
1:15:06
traced through. Now once we hit the end of one of our link lists, we know we just finished the algorithm by taking the remaining nodes of the other list and just tack it on to the end. And that finishing step only takes an O of one time, surely, as soon as one of our linkless runs out, which will always be in general, the shorter one, then I can just finish my algorithm, I actually don't have to iterate fully through both of them. And I would still consider this technically, you
1:15:30
know, some form of a linear runtime. For the space complexity, you can see how the space here is just constant, right? We're not actually creating any new nodes, we're simply rerouting all of these next pointers. And in terms of our variables, we only use a fixed number of them. And so overall, this seems like a reasonable strategy, what I want you to do is try to code up this one on your own, it's going to be some really interesting code, a new pattern for us that is,
1:15:54
and if you get stuck, I'll catch you in the walkthrough videos. See you there.
1:16:01
Hey, programmers, Alan here, right now I want to go over a JavaScript solution for this Zipperless problem. So we'll jump right in, hopefully watch the approach video. And we'll start with an iterative version of this, the way we're going to attack this one is by doing our classic linkless traversal. But do it twice over for a head one and head two simultaneously, really. So I'll set my let current one, start at head one. And I'll also set let current to
1:16:28
the start at head two. And I'm going to need my main loop just to iterate through the linkless. Second check, while current one is not no. And current two is not at all. So notice, as soon as one of my linkless hits its end, this loop would actually stop, right? Cool, we want to be sure to do is set up also a way to create the output. So look at the prompt, we always start with the first node of list one. So in this particular example,
1:17:02
I'm zippering, ABC and XYZ, I always start with the a here. And we're going to use that to get the ball rolling on my resulting list, we're not going to create any new nodes. But we do have to rewire all of these next pointers. So what I'll say is maybe, let's
1:17:20
say head over here, and this will be the head of our output, because I know I need to return that by the end, something like that, I'm going to start head really as head one, technically, and then current one will actually have to start one after that, like we said in the approach. So I'll set current one equal to we'll say, head dot next, that'll be a good starting point from there. And in addition to having this a head pointer, that's because I want to return,
1:17:52
you know, the new head of billing class, which I guess would be the same as head one as I think of it. So maybe we don't need this variable. But we do need is a pointer that we can append after, right. So I'm going to say left tail, I think as a matter of fact, when I set tail equal to
1:18:09
head one, say no head, one's going to be the first note in my output. And over time, I need to add things after the tail building up my resulting list. So that's looking pretty good. Now we'll go ahead and increment our counter, add that into the mix here. So we'll say let count beginning at zero. And dependent on whether or not our count is even or odd, that can tell me whether I should take a node from list one or list two. So I think we're ready to hop into
1:18:41
our main code over here. I know I should end any particular iteration by of course, incrementing, the count, right? Count plus equals one, I'm just going to put that down there. So I don't forget. And I will start by checking the parody of that count, right whether or not it's even or odd, so I'll simply check if count mod two is equal to zero, right, so that means it's even an else it's odd. So bear in mind, I started my output list with a note from head one from list
1:19:12
one. And initially, I start my count equal to zero. So I guess when my count is zero, I'll take something from list two. So what I can do is take whatever current two is pointing at, so current two, and I want to make that the next of the tail, right tail is helping me build the output. So simply tail dot next equals current to nice. Then from there, since I just used up something from list to I need to progress that so current to equals current to dot next. And I know
1:19:47
that this code over here, when it's odd, it's going to be symmetric, just for current one.
1:19:55
And in addition to that, we need to make sure that we also move our tail pointer that's going gonna happen in either scenario. So I can put that mutual code over here, I think I'll say tail equal tail dot next. Nice. So this should help me construct my alternating pattern. But we have to worry about is based on my while loop, this while loop is going to terminate or end, as soon as one of my current pointers hits null. And it could be the case that only one of them is null, and
1:20:24
the other one is still pointing to some data. And like we said, in the approach, what we should do is just tack on all of the nodes of the other list to our final output here. So what I'll do is I'll check here, right? If, let's say, current one foot still has stuff, so it's not equal to know that I can just take that stuff and add it to the tail. So tail dot next equals current one.
1:20:52
And symmetric for current two, of course. So I'd look at the prompt over here, we're thinking about a scenario like this one right here, we know that current one is way longer than current two, or list one is longer than list two. And so by the time we get to the end of list two, we know that roughly we're going to be at about this C node or this D node in list one, we just want to take all
1:21:17
those remaining elements looks like D, and add it to the end of that list. Notice I just end in DEF. Cool, and we just need to check both sides of that. Awesome, I think at this point, let's give this a nice test run. Gonna always debug it together. It's not too long of some code, but it does have some interesting patterns. Awesome. Here, we have a nice iterative solution for Zipperless. For this code, we're looking at linear runtime, and constant space. And so
1:21:45
I think what we'll do is, let me also show you how you could solve this one recursively. It's very similar and strategy, somewhat shorter code. I'll leave it to you whether or not you think it's more simple or not. We will have to concede, though, that for any recursive code, especially for this one, we're going to have some additional stack space used. So we would have a linear space for recursion as well. So I'm going to do my best to translate these
1:22:11
patterns. So I know I should stop my recursion will say if head one is no, and head two is no.
1:22:21
So that's very similar to what we just said in our iterative version. And if there are no, then you kind of at the end, you can just return null. What I have to be sure I do is for my function needs to return like the new head of the linkless. And so I'll just have some base case here, where I return null is basically a linked list contains like many sub lists, right? What you should be doing as you solve linkless problems. Recursively is, if you think of let's
1:22:50
say this as a linked list, going from A through Z, then going from x to z is also linked lists going from B to Z is also a linked list. So that's how I kind of break down my problem size. So if they're both null, then return null. But what if only one of them isn't? All right. So what if head one is no. All right? And that would mean if head one is the only one, that's all that means had to have some stuff, well then just return the remainder of had to make that symmetric for
1:23:21
the other side, right? So we've had two is nil. And had one isn't, then just return the remainder have had one. And what this base case or these base cases will let me do is accomplish some logic, just like this, right? How can I take all of the leftover nodes in the case of one of my lists running out and just tack it on to the end? Right, if one of my pointers runs out, I'm just gonna return the other pointer. Cool, which would be the leftover chain. Now I need my
1:23:50
recursive code. So there are a few ways you can write this. Instead of using the modular trick and checking for even or odd, what I should be able to do is take two notes at a time here. So let's say I know I need to make my head head one, really. So I'm going to return head one, I think at the end, and I need to make head one dot next point two, whatever had to is, right. And as soon as I do that, I would actually lose access to the original head one next,
1:24:21
so I should have saved that. So I'll say maybe const. Next one equals had one dot next before I overwrite it. And I guess why not. While we're here we'll also do the same for next to pretty common thing we have to do for a linkless problems right before you overwrite a pointer, maybe save it in case you need it still. So I'm making head one next point to head to and then from there. I know I need to call recursively zipper list on next one.
1:24:49
And also, next to it should be right. And then from here, I just chained head one to two. I know Zipperless is going to return In the head of the remaining linkless, I just need to chain that
1:25:05
to head to so had to dot next equals that return value, because again, I'm going to return a node from this recursive call. So this code is looking pretty good. Let's go ahead and test it, it is quite a bit shorter. So we're getting error Zipperless is not defined. Because I s here, that's on me. Give that a go again. little typo there. Nice. And here, we have a nice recursive solution for this. And so just to make sure we're on the same page here,
1:25:39
maybe it's worth stepping through at least one iteration together. And so let's say I had these lists had ABC and XYZ, trace through at least one stack frame of this. So ABC, and then x,
1:25:52
y, z. Alright, so I know in the context of my pointers, I have h1 over here, right, that's going to be head one. They also have head two, of course, so h2 over here. And what I do is, I'm not hitting the base cases for this, because I have two nodes. And so we save some pointers to their next. So nothing fancy here, I have next one over here, I have next to over here. And in the core logic of actually alternating, what I do is I take head ones dot next and point it to head
1:26:26
to. So I don't want to just kind of merge them together in line over here. So kind of separately, although you know, I'm not creating new nodes would look like this head one is a, I said it's next to x. So that already looks good to go. And then from there, I set head twos next to whatever the recursive call is, when I pass along, next one next to so at this point, I can kind of ignore these. Right? So I'll take out just this a node. And now h one, or head one points to
1:26:59
be the same thing over here. H two points to y. And let's say we step through this iteration, well, same thing. I just take head one, and I know I'm going to return head one, right? So eventually it's going to return over here. It's going to say B points to why, right? Because head one is B h two is wine head one that next equals head two, and that's good to go.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat