Linked Lists for Technical Interviews - Full Course
Linked Lists for Technical Interviews - Full Course
Learn how to solve linked list problems for coding challenges and interviews.
✏️ This course was developed by Alvin Zablan from Structy. Check out his channel: / alvintheprogrammer
🔗 Study more data structures and algorithms with Alvin in his complete course: https://structy.net/
⭐️ Course Contents ⭐️
⌨️ (0:00:00) Course Introduction
⌨️ (0:01:09) What is a Linked List?
⌨️ (0:09:22) Linked List Traversal
⌨️ (0:23:36) Linked List Values (https://structy.net/problems/linked-l…)
⌨️ (0:33:10) Sum List (https://structy.net/problems/sum-list)
⌨️ (0:42:31) Linked List Find (https://structy.net/problems/linked-l…)
⌨️ (0:51:03) Get Node Value (https://structy.net/problems/get-node…)
⌨️ (0:59:32) Reverse List (https://structy.net/problems/reverse-…)
⌨️ (1:09:50) Zipper Lists (https://structy.net/problems/zipper-l…)
🎉 Thanks to our Champion and Sponsor supporters:
👾 Raymond Odero
👾 Agustín Kussrow
👾 aldo ferretti
👾 Otis Morgan
👾 DeezMaster
—
Learn to code for free and get a developer job: https://www.freecodecamp.org
Read hundreds of articles on programming: https://freecodecamp.org/news
Content
0.08 -> A linked list is a common data structure
used in software development. It is also a
5.28 -> frequent topic in technical coding interviews.
In this course, Alvin will explain linked lists
11.76 -> and prepare you to use them both
in interviews and coding projects.
18.56 -> Hey, programmers, Alf Infrastruktur, here, welcome
to our course on linkless. What I want to do is
23.52 -> really get you well prepped for those linkless
problems on your technical interviews. So consider
28.08 -> this a little bit of a crash course, like I do in
all of our data structure and algorithm courses,
32.64 -> I want to go through two pieces of information
for every single problem. That is I want to really
36.8 -> draw things out visualize things and understand
the theory behind a problem before I go ahead
41.76 -> and implement the code behind it. Right, so we're
gonna do a one two punch for every single problem
46.88 -> here. So this is going to be an introductory
course on linked lists. So I'm going to assume
50.64 -> you know nothing about linked lists, but you're
not a total beginner to programming, right. So you
54.56 -> understand things like a while loops, for loops,
if statements and all that jazz, I'm also going to
59.52 -> assume that you know, a little bit of recursion,
because I'm going to show you some recursive
62.64 -> solutions for many of our linked list problems.
And so without further ado, let's jump right in.
68.56 -> So what I want to do is start by understanding
what a linked list is at a high level bird's
73.04 -> eye view. The first thing we'll need to know is
that a linked list is a type of data structure,
76.72 -> right? So we're organized as data. And in
particular, a linked list is made up of
80.48 -> many nodes. So as the first checkpoint here,
we need to first understand what a node is,
85.52 -> you can think of a node as just a container for
some data. So when we conceptually visualize
90.56 -> nodes, you really think of them as some
circles that I can put some data inside
94.32 -> here, I'll put a letter or character inside of
my node. But of course, you can store any data
98.64 -> you like. It could be a strings, numbers, Boolean,
or even other objects, right. And I'm saying that
104.8 -> a linked list contains many nodes. So let's say
had a bunch of nodes, and they can all contain
110.56 -> different pieces of data. So I have the characters
ABCD, stored in different nodes over here.
116.08 -> And if I wanted to make these nodes comprise a
linked list, then what I need to do is add some
121.36 -> links. In other words, if I have a node like a, I
can make it point to the next node, the dataset,
127.68 -> that is a points to B, right, can also say that
B points to C, and C points to D, right. And the
134.32 -> term we actually like to use for this is really
saying that A is next is B, right? It's going
138.96 -> to be very common linkless terminology, and a
pattern we're definitely going to see in the code
143.84 -> later on. And now you can already see why you call
this data structure, a linked list, right, have
148.32 -> a bunch of nodes linked together. The important
thing to note here, it's about the last node D,
152.96 -> right? D is the last node in our linked lists.
And so under the hood, we can really represent it
157.6 -> being the last node, by having its next pointer
pointing to nothing or more programmatically,
162.64 -> you can have its next set to null, right, the null
pointer and whatever your language of choices.
168.32 -> So sometimes during this course, I'm
going to explicitly choose to dry out
171.52 -> the null note or the null reference, just
so that we can build some very robust code.
176.56 -> Alright, now that we know what a linkless looks
like, I want to introduce some other terminology
179.92 -> that you're going to hear, right. So when we refer
to the very, very first node of linkless, that is
184.72 -> the a node in this diagram, I consider that the
head, it's a very common term. And a similar way,
190.56 -> we can refer to the very last node in a link list
as the tail, right. So if you hear those words,
196 -> in problems, we're referring to the first
node and the very last node respectively,
200.64 -> right? If you think about it, because I have this
sense of different nodes, and you know, a first
205.28 -> note and a second node, but you can think of a
linked list as an ordered data structure. In other
210.4 -> words, if I started at the head of the linked
list, I can just look at this nodes next pointer,
216.08 -> and I can go to the B node, so I can just
move to the right. And once I'm at the B node,
220.16 -> 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
225.6 -> goes to the null node, which must mean that I'm
at the end of the linkless. So that's a very,
230.48 -> very key characteristic about the linkless. Right?
A nice property to leverage about a linked list is
235.44 -> that it's an inherently ordered data structure,
right? If you want to refer to like the positions
240.4 -> of these nodes, and we do that programmer thing
of starting at zero, I can see that the head has
244.48 -> a position of zero, B has a position of one, and
then we just go sequentially throughout, right.
250.16 -> So there are four nodes within this linked list,
I can see that the position of the head is zero,
254.56 -> and the position of the tail is three. So so far,
we're probably not seeing the full value of the
261.12 -> link list, like when would this data structure
have some real utility over other data structures
265.68 -> that we know about? In other words, you're
probably wondering how a linked list compares to
269.36 -> an array because an array is also an ordered data
structure. So let's do that comparison right now.
275.76 -> So here I have my linkless up top, if I wanted
to represent you know, a similar data structure,
280.56 -> but in an array form, it would look something
like this, right? I have an array in memory.
285.36 -> And I know that that array has some indices,
right. So this is a really clear analogy here.
290.16 -> I know that the indices of an array correspond
to the positions of the nodes of a linkless.
296.48 -> Right. And obviously my link was is made of
many nodes. Whereas my array has many elements.
305.2 -> The most important difference between an array
and a linked list is that an array must be stored
310.08 -> contiguously in memory, that means all of your
elements in an array are going to be stored like
315.36 -> right next to each other in your computer's
memory. And that has a lot of consequences
319.84 -> in the runtime of different operations
across your array. Right? So let's say right,
324.48 -> now I wanted to step through a scenario, let's say
I have the goal of inserting a new element Q at
330.8 -> index two of my array. And the key specification
here is I want to insert Q at position two,
337.2 -> I don't want to overwrite the current element
at position two, right? So at the start of
342.48 -> this operation, I have four elements in my array
ABCDE. After I do my insertion of Q, I should have
349.36 -> five elements in my array, and they should go A B
QCD, right, because I'm inserting some new element
355.68 -> at index two. So how will this algorithm run at
a higher level in an array? Well, typically, all
361.44 -> you need to do is obviously find the index two,
which is right here. And I know that this is where
366.88 -> I need to put the new Q element, but I can't just
overwrite this value of C, because I want to do an
372.48 -> insertion not overwrite. And so what happens under
the hood in your programming language, when you
376.72 -> perform this insertion operation? Well, we hope
that there's still some empty space in the array,
381.76 -> and it should occur after D, right. Assuming that
there's still space in this array, I would need
386.96 -> to shift all of the elements to the right over by
one index. In other words, I need to put d to the
393.68 -> right, I need to put c over a one position to the
right. And now I have perfect room to add this cue
399.68 -> at index two. Right. And of course, now D would be
occupying a new index of four logically. But the
406.8 -> important step we took here was to actually
insert somewhere in the middle of an array,
412.16 -> that could mean that you need to shift over a
bunch of different elements in your array, right.
417.76 -> So in this very small example, I only had to move
over to elements of C and D. But let's say you had
422.24 -> a very long array, and there were, I don't know,
1000 elements after your insertion index, you
427.12 -> would have to shift all of them over one by one.
And that is a relatively costly and slow operation
433.12 -> for such a simple move of inserting Q, right.
So we say that when we insert into an array,
439.36 -> that does have an O of n insertion time, right, in
the worst case, if you insert at index zero of an
445.44 -> array, that is you're inserting a very first new
elements, you would have to shift everything over
450.56 -> by one index in the array. And since there are n
elements in the array you're doing and different
455.36 -> shifts. Awesome. Now let's compare that to a
similar insertion operation for our linked lists.
461.28 -> So let's say I still wanted to insert the value
of queue at position two of my link lists. Well,
467.6 -> that means I need to create a new node in
memory. And what's great about a linked list is
472.8 -> it is not required that the nodes are
contiguous in memory. In other words,
477.28 -> we can have these like nodes exist anywhere in
the space of our computer's a memory addressing.
483.52 -> And that's kind of a very low level statement. But
the consequence of this is I don't need to do any
488.48 -> shifting when I perform this insertion. In other
words, how does that work? Well, if I want Q,
494.08 -> to be composition to have my link lists, now
that I've created the new Q node, I just need
498.56 -> to adjust B's next pointer. So I'm going to
look at node B, and reset its next pointer
505.36 -> to point at q, then I set Q's next pointer
to point at C. And with those small changes,
512.4 -> I've actually changed, the logical order of
nodes within my linked list would now be this.
518.48 -> Right, queue occupies position to see occupies
position three, and so on. And what's really
524.48 -> great about this is, let's say that there
were many nodes after my insertion position,
528.8 -> let's say there were 1000 nodes, but wouldn't have
to actually modify all 1000 nodes that came after
534.32 -> my insertion point, I just need to change about
two pointers every single time. Because that's
538.56 -> a constant number of operations. I will say that
a linkless insertion, if we write it correctly,
543.92 -> will be constant of one time. So here we see
a very tangible difference between our linked
549.12 -> list data structure and our array data structure.
And there are many more a different pros and cons
554.4 -> between these two. But for now, we'll leave it
at that and we can chat more about them as we go
558.56 -> throughout the course I'm sure it's going to come
up. But what I want to do for now is talk about
563.28 -> the core core core, a linked list algorithm
that's just traversing through a linked list.
569.12 -> In other words, how can we just touch and
process every node within a link lists?
575.28 -> Well, the important thing to know is if you wanted
to, like give a link list to someone or in other
579.84 -> words programmatically pass a link list into a
function, you really only need to pass a reference
585.28 -> to the head node of a linked list. Because
if I give you the head node of a link lists,
591.12 -> by accessing the next property of every
node, you can have access to the full
595.44 -> sequential list, right? And so to actually
implement a traversal algorithm on a list list,
600.56 -> we just need a handful of variables. Most
importantly, we need like a current variable,
605.12 -> a current reference to look at the current node
of the linked list we're iterating through,
610.48 -> 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
616.32 -> current dot next, right or something similar
in the programming language of your choice,
620.96 -> I can just set current equal to current dot
next, then I would be at the B node. And B also
627.36 -> has an XT. So I do that again, at the C node,
I can just keep continuing this process, right,
632.56 -> assigning current equal to current dot next,
until at some point, once I'm at roughly the tail,
639.12 -> current would be D. And so current dot next would
be this null node or this null reference. And if I
644.8 -> set current equal to next, I'll be right at null.
And that can be a perfect condition I can catch.
650.16 -> In other words, we can stop the algorithm when
current is equal to null, we know that that
654 -> point would have visited every node of the link
lists. So as I went through this high level trace,
659.28 -> I was kind of speaking upon this algorithm as if
it was an iterative solution. And I'll also show
664.32 -> you how you can solve this one recursively, it's
really the same line of thinking. At this point,
668.56 -> I would want to actually hop into some code. So
we can see the nuts and bolts implementation of
672.88 -> a link list as well as the core traversal
algorithm through a linked list. Alright,
677.52 -> let's do this. So here I am, in my text editor,
I'm going to be doing this in JavaScript,
682.08 -> although you shouldn't be able to follow along in
your language of choice. So the first thing I want
686.24 -> to do is just manually build a linked list. And to
start, I'm going to need to create a node class,
691.76 -> right, so we're gonna stay a little bit
object oriented here, just create a node
696.32 -> class. So from JavaScript, I need to give it
a constructor. And in terms of the properties,
701.2 -> we're going to need to store inside of an instance
of Node, I only need two things, I need to store
706.24 -> the actual value. But I also need to store a
reference to the next node in the linked list,
712.08 -> if there even is an x node, right. So to my
constructor, I'm just going to take in the value,
716.64 -> so I can say this dot val equals Val. And I'm just
going to always initialize my next to be null,
725.12 -> right, I can just manually reassign this next
property. And if you have this class or in it,
730.96 -> that's all you need to start creating some
linkless. I'll be it manually. So let's say
735.04 -> I want to construct a linkless, I'll just create
a few instances of nodes, I can create node A,
740 -> make it a new node, I need to pass in the value to
be constructed, I'll just give it some characters
746.4 -> here, maybe some capital letters this time. So the
character a lot create a bunch of nodes like this,
752.32 -> it's will have my B, my C and my D. I'll give them
some corresponding values. Naturally, I'm storing
760.16 -> strings or characters within the values of my
linkless. But you can make them you know, numbers,
764.32 -> if you want, it's no big deal. What I want to do
now is actually link these nodes together, that
769.92 -> way, I can just have a linked list, I can start
writing a few algorithms on, right. So typically,
774.16 -> this part would be kind of taking care for you
already. If you're on an interview, you can assume
778.16 -> that you're taking in a properly structured link
lists. But if I want to just like test some code
782.56 -> for myself, what I can do is say things like A's
next is going to be equal to the B node, right.
788.48 -> So I'm making A's next property, now become the B
reference. So I'm actually linking these two nodes
796.88 -> together, right? A's next is pointing to be the
same way, these next is pointing to C, C's next is
803.12 -> pointing to D. And there is no other nodes in my
linked list, I'm going to leave D alone. Because
808.96 -> I know automatically, these next would currently
be pointing to null, which does represent the tail
814.24 -> of my linked lists. So like visually, I think
of this sort of structure, I have a is my head,
819.04 -> that points to B, which points to C, which
points to D. And technically, D points to like,
825.36 -> no, so I'll be explicit here and just draw
that one out. Nice. So now that I have my
832.08 -> link list ready to go, let's go ahead and write
our traversal algorithm on it. That is I just want
836.72 -> to iterate through every node of the link lesson,
maybe just print out the value, something very,
843.04 -> very foundational here. And so all maybe choose to
make this its own function, I think that'd be the
848.32 -> best way to go about doing this. So I'll create
a nice function here, I'll call it just print
854.4 -> linked list, it's going to take in the head of
olink list, I'm going to stay kind of abstract
860.4 -> here. And I just like to call it head, right.
There's my nice empty function. And in terms of
866.4 -> how I would actually want to call this function,
the client would have to call print linkless.
871.6 -> And give it like the real head of the link list,
which for me in my little example here is just a
876.24 -> reference to the a node. Cool, so I'm actually
receiving the head node, which is an instance
881.36 -> of Node as the head of my link list here. And
so let's go ahead and now set up our algorithm.
888.24 -> So we're gonna really just implement the
algorithm we just traced out on the whiteboard.
892.32 -> So if I want to just traverse through a link
less and print out every node, I'm going to need
897.04 -> to continually update a current pointer. So I'll
say current equal to the head of the link lists,
903.92 -> which means I'm really starting at
the very beginning of my link lists.
907.68 -> And then from there, how far do I need to go
while you want to keep running this algorithm
911.44 -> while your current pointer is not equal to no,
right? Because if current is not equal to null,
918.56 -> then there's some stuff to still iterate through.
And now we get into the meat of the algorithm.
924.24 -> If I wanted to, like print out or process my
current node, I'll just console dot log here,
928.96 -> we're going to print out this current nodes value.
Right. And notice I'm writing all this logic in
936.64 -> terms of current, because I hope to update current
properly at the end of every iteration. Right. So
942 -> now that I printed out current vowel, what I want
to do is update what current is pointing to. So
947.84 -> what I should do is set current equal to current
dot next. And don't be fooled here. This is a very
953.2 -> simple variable assignment. Right? So let's run
this code. And then I promise that I'll trace
959.12 -> through how this actually operates. It's very
short code, but really the foundation of most
964.48 -> linklist algorithms. So let's give that a run
over here. I hope to print out my characters
969.52 -> ABCD. Awesome. And there I have them. So how does
this code work? Well, let's try to update and
975.04 -> annotate this drawing as we step through the exact
code here, right. So I know that in the context of
980.88 -> my function over here, I'm really only going to
track a really important variable of current. And
985.76 -> that starts at the head of my linkless, which
is passed in as the a node. So technically,
991.04 -> give myself some room here, I would say that
the current variable starts by referencing
998.08 -> the A note, so I'll kind of represent like
that it's aligned horizontally, right.
1002 -> Cool. And what I want to do now is consider my
condition. So my condition is checking right?
1006.72 -> While this current variable is not equal to
null, then run the code inside of the while loop.
1011.6 -> So if I check that on the first iteration of that
condition is true, right, current is not equal to
1016.24 -> null. So I can run the code inside, which means
I just print out the value of the current node.
1022 -> Right? Since current is an instance, of node,
when I do console, log current dot Val, I will
1027.12 -> be printing out the A that was initialized inside
of it. So that gives me my first iteration.
1032.72 -> Now here's the important part. Right? Now,
I know that current is A, so in this moment,
1038 -> that means current dot next would be actually
referring to the B node. So if I set the current
1045.28 -> equal to current dot next, it has the effect
of literally moving this over to the B note.
1051.04 -> Now I can check my condition again, is current
not equal to No, that's true. So I print out my
1056.16 -> current value of b, and then go to the next. At
this point, the process just continues, right?
1061.52 -> The C note is still not equal to null. So
I print it out over here and go to the next
1066 -> node of D. And this is still true, right? D is
not equal to the null. And so I print out D.
1072.88 -> And I actually proceed another iteration,
right. So right now current is D,
1077.36 -> current dot next is null. So this would
literally happen, I set my current equal
1082.32 -> to no. But things work out great here, because
when I check this condition, I'm going to check
1086.64 -> is current not equal to null, in other words, is
no not equal to null. And that's false. So I exit
1093.28 -> my while loop. Right. That's how I'm able to print
out every node of my linked list, right ABCDE.
1100.16 -> So I think something to draw your attention
to right now is how we write this condition.
1104.96 -> I think the best way and the most robust way
to write this code is to check while current is
1110.88 -> not equal to null. The most common mistake I see
people make is they don't like generally that your
1116.64 -> condition should be about like roughly the tail
of your link list. And so they might try to say,
1122.4 -> well, current dot next is not equal to no.
Right. But that would actually cut your iteration
1128.16 -> short. If I ran that, I would only really print
out ABC, right? Because when I'm at the D node,
1136.08 -> right, I would be checking all right, before I
even print out D. What's these next? Well, these
1140.96 -> next is no, so I won't even print out D, which is
bad, right? So generally, when you try to write
1147.92 -> your algorithms, especially about linkless, try
to write it as like present as possible, right.
1152 -> So I'm not going to do any premature checking of
the next node, unless I really, really have to,
1157.84 -> instead, it's better to actually go to the
next node, and then exit when you actually
1163.12 -> are at the null pointer, right, the null node.
So let me return this back to its former glory.
1168.56 -> And we'll just make sure that this still works
is our classic implementation of a linkless
1173.6 -> traversal. It's going to be the baseline code for
almost all of your linklist algorithms. Let's take
1178.72 -> this a step further. And I'll show you how you
could write that same logic, but recursively
1184.16 -> it's really the same logic, you just turn it into
a recursive call and a base case, right? So let's
1188.64 -> go ahead and do this one together as well. When I
promised in the next section, I'll give you a nice
1193.84 -> problem to work through. And so if I want to frame
this one recursively What do I need to do? Well,
1198.88 -> I like to start with my base. case, your base
case should basically be an analogy for like the
1203.84 -> condition you wrote inside of your while loop. In
other words, when are you done with the algorithm?
1209.76 -> Well, I'm done with the algorithm once. I'm
looking at No, right? So I'm going to say, if head
1217.04 -> equals no, then I'm done. So just return.
1222 -> Notice that here, I'm keeping this argument
named as head, because I think of a link list
1227.2 -> as containing many linked lists. In other words,
A is the head of this link lists. But if I look
1233.44 -> at the sub list inside B, is the head of its own
linkless, as well, right and see, is the head of
1238.8 -> a smaller linkless. Still. So I think that's okay,
terminology to use for a recursive function really
1244.56 -> shows that you're buying into the recursive nature
here, right? Awesome. So I'm going to stop running
1249.6 -> and just return out, once my head is looking at
null. So that'd be once I'm at this point, right.
1255.76 -> But in the recursive case, what I want
to do is actually process this node.
1260.08 -> So if my head is not equal to null, right now,
then I'm over here, right? What I should do is
1266.08 -> just print out this nodes value, right, just like
I did before, I'm just reframing current data set.
1273.76 -> And if I want to actually progress to the next
node, like I did, in my iterative solution,
1278.4 -> I just do a very proper recursive call here.
So I'm going to call the same function actually
1283.44 -> makes it recursive. And what should I specify as
this argument? Well, I just want to give the next
1288.72 -> node in the linked list, right, so I'm passing
in head dot next. And that would be all I need
1295.6 -> to do for this one, very, very short and to the
point. So let's run this recursive function,
1300.48 -> then I'll help you trace through it a little
bit more awesome. So it's working, the trace
1304.88 -> looks almost the same. But I think it's good if
we do it side by side with the code over here.
1309.04 -> And really, the key argument we need to trace
through is the head over here. So on our top level
1316.16 -> call, really passing in the a node as head. And so
I checked my base case here is head equal to null,
1323.68 -> that's false. So I go into this console dot log,
which means I print out the value a, awesome,
1329.2 -> and now I make a recursive call upon the next node
in the linked list. So if head is a, then head dot
1336.64 -> next refers to B. And since I'm making a call to
that next node, in this next stack frame, head is
1343.36 -> B. And I check the condition again, is b equal to
no, that's false. So I just print out b over here,
1349.6 -> and then make another recursive call on B's next,
which is C, right? And this process continues,
1355.76 -> all the way down to let's say, a when head is D,
right? I check this condition is d equal to no,
1362.88 -> that's false. So I go ahead and print out D, which
is like the last logical node in my linked list.
1368.32 -> And I would make another recursive call upon DS
next, right? So of head is D, head next is no.
1375.6 -> And I would indeed make this call. And now I'm
back inside of this new call, and I check his
1381.52 -> head equal to null. And that's definitely true
right now. So I return, that's my base case.
1387.2 -> And I end my recursion, right, this base case,
is really, really important. So I want you to
1392 -> compare and contrast, these two pieces of code,
they really implement the same algorithm. And as
1397.92 -> we go through these linkless problems, sometimes
I'll show you both ways to solve it. depending on
1402.56 -> you know, what style of problem you're solving,
you might find the recursive or the iterative,
1406.72 -> a little easier to write over the other, which is
why I think it's important to practice both, but
1410.8 -> maybe, you know, choose a favorite and decide what
you're most comfortable with. But that being said,
1414.96 -> practice both. Alright, let's head back into the
whiteboard. Hey, programmers, Alvin here, right.
1419.76 -> And I want to go over a approach for this link
list values problem. So hop right in right here,
1425.04 -> this problem is going to be given the head node
of a linked list we want to do is return an array
1430.08 -> containing all of the values within the nodes
of that linked list, we should do it in order.
1435.76 -> Bear in mind in this problem, we're given a Singly
Linked List, which means that every node has a
1439.76 -> pointer to the next node in the linked list, we
know that the last node of the linked list would
1445.28 -> have a next pointer that points to know that being
said, how do we go about solving this one? Well,
1450.8 -> there's problems, we're just going to have to
force you to implement a really core linkless
1454.8 -> pattern that is just traversing through a linked
list in order. And so we'll start by attacking
1460.24 -> this one, maybe with an iterative description.
So let's say we started from ground zero,
1464.4 -> right? So we want to create our values array, and
to the side, we can just initialize values to be
1469.6 -> an empty collection. And to implement this core
pattern of just traversing through a linked list,
1474.56 -> we're going to need a variable or just a
pointer. And we're going to start at the head
1478.4 -> of the linked list, right? Bear in mind
that our function only takes in the head,
1481.76 -> but I know the head is like the ultimate starting
point of the linked list. And eventually I could
1486.08 -> access everything throughout the entire list.
So I'm going to set my current equal to the
1490.72 -> head. And what I can do off the bat is just check
current value and add it to my running collection.
1497.36 -> So I have the a value inside of values now And
since I have access to the current node, I know
1502.8 -> that if I access its next property, I would have
access to the next node of B. So what I can do is
1508.08 -> set current equal to current dot next, basically
just moving my pointer to the next node like this.
1515.36 -> Same thing as before I can add my
current value into the collection,
1519.76 -> I'll just proceed in this way, right, same
thing for C, set current equal to current next.
1525.28 -> And things get interesting once we
approach the tail of this linkless.
1528.64 -> So I'm currently at the D node. And I go
ahead and add that value into my values list.
1533.44 -> Well, we'll have to do now is consider the
scenario when it's appropriate to actually
1536.8 -> stop our traversal. Well, bear in mind that these
next actually points to know. So maybe I'll draw
1543.04 -> that explicitly just for this drawing. So these
next is just pointing to null. Which means if I
1548.08 -> continue this algorithm in the general sense, so
I set current equal to current next, that means
1552.64 -> my current pointer now points to know. And I think
that would be a perfect stopping condition. Right?
1558.64 -> So once current is no, we know that we've hit the
end of our link list. And so we're totally done.
1563.76 -> And if you look at the order of our values,
it is indeed the correct order, right?
1568.08 -> What can we say about the complexity of this
algorithm? Well, if we say that n is just the
1571.52 -> number of nodes in this link lists, then
the time complexity is going to be O of n,
1576.72 -> right? Because we're just are really iterating
through every node once. And our space complexity,
1582.16 -> if we consider the output right now would just
be also linear in the number of nodes over here.
1587.44 -> And I'll tell you what this looks like a pretty
good strategy, we can go ahead and implement
1591.2 -> well implemented in two ways. First, I'll show
you the iterative version, and also show you how
1595.2 -> to implement this one recursively. Really,
both the iterative and the recursive code
1599.84 -> use the same sort of mechanisms. So
I'll see you in the walkthrough video.
1605.68 -> Hey, programmers, Alan here, right now want to
go over a JavaScript solution for this linklist
1610.56 -> values problem. So we'll jump right in. And we'll
start by implementing, I think, the iterative
1615.84 -> version that we spoke about in the approach video.
So if you haven't watched the approach video,
1620 -> definitely make sure you check that out first,
right. And so I'll get the ball rolling over here,
1624.72 -> what I want to do is use a pointer really just a
variable for me, right, so I'll say let current,
1629.92 -> I'm going to initialize it to be the head. And
I know that though, most important pattern I
1635.12 -> probably need for a linked list is just a
traverse in order through a linked list. And
1639.92 -> the way that looks is I want to keep iterating
while my current is not equal to null, right,
1644.96 -> so just not equal to null, no would mean the
very, very end of my linked list. Nice and very
1651.92 -> standard code I need inside is to progress to the
next node of the linked list. So I said current
1657.76 -> equal to current dot next. So now think about
actually generating the return type. For this
1664.4 -> function, I do want to return an array of all the
values. So I should initialize that up top, I'll
1668.64 -> say let's, or maybe const values, because an empty
array. And then as I actually iterate through all
1676.08 -> of my nodes of the linked lists, at the tippy top
of this while loop, I can just take my current
1681.52 -> nodes value, right, every node has a dot Val and
also dot next I'll take the current nodes value,
1687.52 -> and just push it into values, right? So values dot
push, that single Val. And once this while loop
1694.32 -> is done running, I must have hit the end of the
linked list. So I can just returned the complete
1700 -> values array. So before we run it, one thing I
want to always emphasize is for your link list,
1706.8 -> a main logic, it's always important that you try
to write your logic about just your current node.
1713.28 -> So for example, my condition is saying, while
current is not equal to null, it doesn't say like
1719.36 -> while current dot next is not equal to no, right,
you can probably get away with finessing code like
1725.04 -> that, but ends up being more clunky than anything.
In other words, whenever I try to write my logic
1730.48 -> for linked lists, I always try to stay very
present, right, so just worry about your current
1734.64 -> node. So what I don't like to see is patterns
like this write current dot next dot Val, and try
1740.56 -> to just shift your frame of reference because if
you do that, then you're actually kind of assuming
1745.04 -> that your linkless has a particular length.
So instead, I always try to write all of my
1749.92 -> expressions about simply current, right, so
while current is not equal to null, then I
1754.48 -> push current dot Val. And then I can just update
current to be current next. And I can be assured
1760.72 -> that every node is going to be processed in this
algorithm. So let's give this a test run now.
1767.28 -> And if all is well, we can transition into the
recursive version now. Awesome. So how can we
1773.84 -> do this recursively I'll just do that down below.
So the way I would structure this one, just so I
1778.48 -> get the most optimal complexity is really with two
functions. So my main function will do almost the
1785.44 -> same thing. It is going to call a helper function.
I'll call this helper function, maybe fill values.
1791.36 -> And this function is going to actually do the
recursion. So it's going to take in the head of
1795.2 -> the linkless, and also a reference to the values
array. So recall that in JavaScript if I pass
1800.16 -> any non primitive types, so basically, things like
arrays and objects, they are going to be passed by
1806.32 -> reference, right? So what I want this fill values
function to do is to actually mutate the values
1812.48 -> array, because this main function is going to
return it. So what does that recursive function
1816.8 -> look like? So we'll say fill values, it's going
to take in the head, and also the values, right?
1822.88 -> I'll start with a base case here. And really,
what we're trying to do is just translate the same
1828.56 -> patterns from the iterative code just into their
recursive variations, right? And so I know I need
1834.64 -> to stop my recursion, once my head is no, right.
So I'm going to check if head is equal to null,
1842.8 -> then you can stop. So just simply return, right
really important distinction here is, you're going
1848.16 -> to have a tough time and probably end up with some
clunky code, if you say, if head dot next is null,
1854.4 -> right. So again, I always try to stay very
present, and all of my code, so don't worry about
1859.2 -> your next node, just handle yourself, right?
Eventually, every node will get served here.
1864.72 -> So if head is null, then nothing much to do just
return and you can stop your recursion. Otherwise,
1869.76 -> I know that head is not null, so it must be a
node, I need to take that nodes value and add it
1874.8 -> to values, right. So I can say, head dot Val, and
I want to push that into the values collection,
1881.6 -> right, we're call that values is referring
to this outer array here. But beyond that,
1888.56 -> besides this current head, there could be other
nodes right in the remainder of the linkless. So
1894.24 -> I can just call recursively fill values, and
instead of pass along head again, I need to
1898.88 -> pass along head dot next, right. And that means in
that recursive call and kind of jump back around,
1904.4 -> and now head is referring to the next node, and
so on, and then its value is going to be added
1909.6 -> all the way until we get to the very, very last
node. Technically, after D, we would hop to
1916.76 -> these next, which is no, in which case, we would
exit due to this base case, exactly. And before
1922.72 -> we run it, just a few issues that I need to
fix, I see that missing an equal sign here.
1926.96 -> And also when I call filled values, of course, you
need to pass along the same values array, because
1931.76 -> I know that every call wants to add its value into
the same values array there. So we'll give this a
1938.32 -> test run. See what we get. Cool. And now you also
know how to implement this algorithm recursively.
1945.52 -> So the reason I like to split up my recursive
version for this algorithm into two functions
1951.44 -> is so my recursion doesn't actually have to create
like multiple arrays, right? Instead, all of these
1959.04 -> recursive calls are just adding their values to
a single array. If I actually created like copies
1964.64 -> of arrays all the way through the recursion,
I would end up with like an n squared, sort of
1970 -> runtime. Cool. So when it comes to comparing these
two implementations, they're actually equivalent
1977.04 -> terms of their time and space complexity, right?
All right, programmers. That's all I got for this
1980.72 -> JavaScript walkthrough. I want you to practice
both the iterative and recursive versions,
1985.36 -> because they're gonna both be very useful for
the next upcoming problems. I'll see you there.
1993.04 -> Hey, very amorous. Welcome back. Right. Now I
want to go over an approach we can use for this
1996.72 -> some list problem. So in this problem, we're
going to be given a singly linked list containing
2001.36 -> numbers as the values, what you
want to do is return the total sum
2004.88 -> of all the values in the linked list. So for this
particular input, we should return a total sum of
2009.68 -> 20. And so how can we go about solving this really
just reviewing a core linked list pattern, right,
2015.12 -> all you have to do here is just traverse in order
through the link list, and you can accumulate a
2019.84 -> sum. So let's say we start from the beginning.
If we initialize some some variable to zero,
2024.72 -> we can also just use a pointer that starts at
the head of our linkless. And what we can do is
2030.64 -> we can take current value and add it into our sum
just updating the sum. So I take my current value
2036.16 -> of to add it to my sum, by total sum is right now
to that I can set current equal to current next,
2043.44 -> I can add this eight into my sum getting 10. next
iteration, I can add my three into the sum getting
2049.44 -> 13. next iteration, I can add seven into the some
getting 20. Alright, and I know that technically
2056.16 -> seven does have a next pointer, and it does point
to null. So let's say I do that out explicitly.
2061.52 -> What I can do at this point is actually continue
my algorithm. And I can make the stopping
2065.52 -> condition when my current points to null, right.
So in general, we can call this up by saying a
2070.32 -> loop like, you know, while current is not, no,
we talked about the complexity of this algorithm,
2075.92 -> it's pretty straightforward. We're definitely
just iterating through every node. So if n is
2080.08 -> a number of nodes, we have O of n time,
roughly one iteration of for every node,
2084.56 -> and then our space complexity here is actually
o of one if we do this iteratively, right. The
2089.44 -> only variables we need to maintain are really just
current and also the sum variable and we're just
2093.92 -> going to store some primitive values in there. So
we have a nice constant space solution over here.
2099.36 -> So the internet It was really straightforward.
Just for, you know, complete understanding how
2103.44 -> can we solve this one recursively. If you saw that
recursively, that means you have to, you know,
2108 -> call your function many times, and we start
with a top level call on the head node of two.
2113.68 -> And what this should do is really just call upon
the next node, right? So I could call upon head
2121.04 -> dot next session, give me a call to this eight
node, and that should call upon the three node,
2124.64 -> and that should call upon the seven node.
And finally, the seven node should actually
2128.64 -> call upon its next, which would be the null
node. And that will actually act as my base case,
2134.16 -> I think it's a really great one, where I can do
with this base case, right? If my node is null,
2139.84 -> then I can just return zero, right? Think of no as
if it's an empty linkless. What is the total sum
2147.6 -> of an empty list? Well, that would definitely be
zero. So I'm going to plug in this return value,
2152.24 -> right? So I'm saying this call to the null node
is going to return zero. When we say return, that
2158.08 -> means returned to your caller. So the zero would
actually be returned into the seven node, what
2163.6 -> the seven node should do is at its current value,
write its own value into that number, giving seven
2170.24 -> and then that returns up the stack. At this
point, I returned back to the three node three
2175.04 -> can add its value with that seven getting 10 Just
returning that up, eight can do the same giving
2180.32 -> me 18. And finally, two can add itself into that
return value giving us 20. And that would be the
2186.4 -> correct answer, right. So there are plenty of ways
to implement this one. If we solve it recursively,
2191.12 -> we're definitely going to have one call for
every node within our linked list. So that'd
2195.6 -> be O of n time. And the space complexity would
actually be a little more than our iterative,
2200.4 -> we would have O of n space here because of the
call stack. Right? Typically, when we analyze our
2204.96 -> recursive functions, we should include the space
utilize for making these recursive function calls,
2210.8 -> right? So O of n over here. And notice that
when we bought them out at our base case,
2215.68 -> we would have you know, roughly like four or five
things on the call stack. Alright, so those are
2221.2 -> the two strategies, I'll think well code up,
and I'll catch you in the walkthrough video.
2226.48 -> Hey, programmers, Alvin here, right, now I
want to go over a JavaScript solution for this
2230.96 -> sum list problem. So I think we'll get things
kicked off by implementing a iterative version
2236.56 -> for this. So I know I want to create a sum and
add to it over time. So I'll create that variable,
2241.44 -> I'll say, Let's sum equals zero, I know by the
end of this function, I'm just going to return
2246.96 -> that total sum. Now I need to lay down my very
standard code for just traversing through a linked
2253.52 -> list. So I'll say let current, we're going to keep
updating this variable over time. And it's going
2258.72 -> to initialize with simply the head node. And I
know that in the loop for this kind of classic
2266.24 -> linkless traversal, I just want to iterate a while
current is not equal to null, right? If it's not
2272.96 -> equal to null, then it's a node so I can actually
look to its next pointer. So I'm going to need
2278.64 -> this pattern, right set current equal to current
dot next, this actually steps through, you know,
2284.24 -> the link list and sequence. But how do I actually
want to utilize my current nodes value? Well,
2289.36 -> I just want to take it and add it into the sum,
right? So sum plus equals current dot Val. And
2296.24 -> eventually, once I hit the very, very end of the
linkless, I know current is going to be equal to
2300.56 -> null. So I exit the while loop. Now just return
my total sum. So let's run this. Just a little
2306.8 -> variation off of our last problem, just doing
some computation along the way. Nice. And now
2313.04 -> I think I'll show you the recursive version, which
I quite like. So for your recursive version, it's
2319.2 -> all about starting with a meaningful base case,
right? So first thing you think about is alright,
2323.84 -> typically, for my linkless problems, my base case
is about my head being null, right? And that kind
2330.08 -> of represents the scenario where my linked list
is an empty linked list, right? If it's null,
2334 -> that means it has no nodes. So what's the total
sum of an empty linked lists while it's just zero,
2339.6 -> so I'll check if head is equal to null, then
just return zero? It's important I think about
2347.04 -> compatible types here, I know, when my linked
list actually contains some nodes, then I should
2352.08 -> return a number. And even in the base case, I
should return a number. It's just the case that
2356.64 -> I return the number zero. Nice. Let's say now we
write a recursive code, right? If the head is not
2362.32 -> no, then it's actually a node. So I can look
at its value, right? Because the head dot Val,
2367.6 -> what I want to do is take that number and add it
to the sum of the remaining nodes in the linkless.
2373.44 -> How can I get the sum of the remaining nodes
after my current position? Well, that's just about
2377.76 -> calling your function recursively. Right? And
passing along head dot next, right? So always try
2383.68 -> to think about your recursive call for the type
of data that it returns, right? It gives me back
2388.56 -> a number representing the total sum of everything
starting at the next node. I'll take that number,
2394.72 -> add it to my value, and that should give me my
complete sum. So I'll just return it So I'll
2400.4 -> give this a shot. And the recursive code is quite
short. One thing we should consider though, when
2407.6 -> it comes to like an apples to apples comparison
between the recursive and the iterative, um, they
2412.4 -> both have the same runtime, right, they both
have O of n. In the case of my recursion, I have
2417.12 -> N calls in the case of my iterative code I have
and just iterations in the while loop. But the
2424.08 -> recursive version also uses n space, right? That's
because for recursion, we actually have to add
2430.32 -> every function call onto the call stack. So
I know by the time that my recursion bottoms
2435.52 -> out a base case, I would have n calls on the call
stack. Whereas in the case of our iterative code,
2441.04 -> we would actually use only a constant amount of
space because we only use a handful of variables
2446.56 -> here. That being said, I highly recommend that
you practice both of these solutions, because
2451.52 -> depending on the problems that we solve, you may
find a one more natural to use than the other,
2456 -> hey, programmers, before we continue the course on
linkless, I just want to make you all aware of my
2460.24 -> own data structure and algorithm platform that is
struck the dotnet. If you haven't noticed already,
2465.68 -> all of the content that you're launching in this
course, as well as some of my other material on
2469.68 -> Free Code Camp is also on structure dotnet, with a
lot of other topics covered as well. So we go into
2476 -> the course, I cover all of those classic, you
know, data structure algorithm topics with tons
2481.6 -> of videos for every single one. So if you
like my teaching style, I think you'll also
2485.12 -> enjoy structure dotnet. And if you hop into any
particular problem, I'll give you a quick little
2490.4 -> tour over here. So if we go to this insert, no
problem. Like you expect, you can write your code,
2494.88 -> you can view the problem, you can run your
code, see the output, I think most importantly,
2498.72 -> what will bring you the most value is my kind
of signature videos, right. So you're going to
2504.48 -> be able to have a high level approach for
every single problem as well as the code
2509.6 -> walkthrough. So you get the nuts and bolts code
implementation for every single problem. And even
2515.44 -> still, if you're not like a JavaScript, I know
that this free coke and video is in JavaScript,
2519.6 -> you can totally switch the language. So for all
of my C++ people in the crowd, doing so is that
2525.36 -> is switching to C++ would obviously change the
prompt in the text editor. But also, you'd get
2530.16 -> different videos right here you see a C++ specific
video over here, right. So if you've been enjoying
2536.72 -> my content, and just want to check out more
data structure and algorithm material with me,
2540.72 -> head over to structed dotnet. I'll leave a link
to the platform in the YouTube video description.
2545.92 -> And with that, let's head back into our linkless
course. Hey, programmers, welcome back right now
2552.88 -> I want to go over the approach we can use for this
link list find problem, and I'll show you two ways
2557.28 -> to solve this one. So in this problem, we're going
to be taking in a linked list as input. And we
2561.68 -> also have a target value we want to do is return
true or false whether or not the target value
2567.92 -> is contained within the link list. So for this
particular example, I'm asking for a target of C,
2573.2 -> you should return true because C is definitely
within the link lists. In another scenario,
2578 -> let's say I gave you a target of G. And that's
an error, you would just return false because
2582 -> g is not a value of this linkless. To solve
this one, we're just going to use our classic
2587.52 -> linkless traversal algorithm. So we'll step
through it as if we're looking for C. So in
2591.76 -> the long run, we expect to get back a true here.
Well, I know that they're going to give me the
2596.08 -> head of the linked list as input, and I'll create
a current variable that points to the head node,
2600.88 -> of course, I'm going to progressively update this
current variable to be the next node over time,
2605.68 -> right? So what I can do is whenever I'm situated
at some current node, I can check if my current
2611.28 -> value is equal to my target value. So right now I
would check is a equal to see it's not. And so I
2617.68 -> should keep looking through the link lists. I know
that current also has a next property. So I'll
2622.88 -> update current to be current dot next, and then I
check is b equal to C? It's not. So I keep going.
2630.08 -> And finding that can hit a point where I see that
my current value of c is equal to my target value
2634.64 -> of c. And so I can just do an early return true,
right? Once I find a match within my linked lists,
2640.56 -> I can just return my final answer. Now let's
say we had the opposite scenario, let's say
2645.12 -> that my target was G, we're going to start the
algorithm and the same way we start at current.
2649.76 -> And we keep looking through the linked list. And
we set current equal to current next, eventually,
2655.2 -> we know that current is going to be equal to null,
which sort of signifies that we've hit the very
2660.64 -> end of our link lists, right. And at this point,
once we finish iterating through the entire linked
2665.68 -> list, we know that we didn't see the target value
because we were checking the entire way through.
2669.84 -> And so at this point, we can do return false.
This is a really practical programming pattern,
2674.72 -> right? Where we check some conditional inside of a
loop. And if we find something we're looking for,
2678.72 -> we'll return true early. And afterwards, after
our loops done running while return false late.
2685.2 -> We talked about this iterative strategy, we know
that if n is the number of nodes, we're just going
2689.68 -> to iterate through every node of the linked
list, so we would have a runtime of O of n.
2693.84 -> And our space complexity here would just be O of
one because we're just using a constant number of
2698.56 -> variables. So That was the iterative solution,
how can you also solve this one recursively.
2704 -> So let's say we were looking for the target of
C, and we had a more recursive point of view.
2708.64 -> So we know we're going to make a top level call
on the head node of our linked lists. And I can
2713.68 -> just think about some base cases to use here,
right? And I know I need two base cases, right?
2718.24 -> One that can return true, and another that can
return false. So for my first base case, I can
2723.76 -> just simply check, alright, if my heads value
is equal to my target, then just return true.
2729.68 -> And the opposite scenario, let's say that my
head is no, then I should just return false.
2735.04 -> What I always try to do with my recursive code
is the thing about my base cases as if they're
2739.2 -> their own valid inputs. So in particular,
for base case number two, if head is null,
2744.16 -> then that kind of represents the empty linkless.
If my linked list is empty, then I can return
2749.76 -> false because I definitely can't find the target
within an empty linked lists. So how would this
2755.44 -> run for current input of targets C? Well, I would
check, alright, is a my target it's not. So I make
2762.64 -> a recursive call upon B. Same thing, right? It's
not make another call upon C. And at this point,
2768.64 -> I see that my current heads value is equal to my
target. And so this node is going to return the
2773.6 -> Boolean true. And I know that this return value is
going to return back to its caller of B. And then
2778.96 -> B is going to pass it back up to a and of course,
a returns it to the very, very top level call.
2785.2 -> Let's say we had a scenario where a target
was not found within the linked list like G,
2789.36 -> then we can see the other base case fire at the
very end, right, so I'm going to make a call on a,
2794.56 -> a calls B, B, call C, I still find the value
2799.04 -> c calls D. And finally, when D looks at its
next it's going to pass along Nol right,
2804.64 -> because these next is technically no. And at
this point, I just hit base case number two,
2810.16 -> so I can return false. And like before
I return these values up the call stack.
2819.68 -> When we talk about the complexity of this
recursive algorithm, we can say that n is
2823.04 -> the number of nodes, we're definitely going to
have O of n runtime, because we make a call for
2827.6 -> every node of the link lists. But we also have O
of n space, right? Because each of those calls by
2833.44 -> the time we bought them out at a base case, we
would have to store those on the call stack. We
2838.72 -> know that the worst case scenario is if our
target is not found within the link lists.
2845.6 -> That being said, I think these are two fair
algorithms to go ahead and implement. So give it
2849.28 -> a shot on your own. If you get stuck. I'll catch
you in the walkthrough videos. See you there.
2854.8 -> Hey, programmers, Alvin here, right
now I want to go over a JavaScript
2858.16 -> solution for this linkless find problem. So we'll
jump right in. And I'll start by showing you all
2863.28 -> the iterative solution. And so we'll start with
our pointer variable, we'll say let current equal
2869.12 -> the head. And we'll just lay down the foundation,
right? We know we always need to iterate,
2873.52 -> while current is not equal to no. And while it's
not know, if we want to progress to the next node
2880 -> of the link lists, just set current equal to
current dot next. Now I just need to work in
2885.44 -> the logic specific to this problem, right. As I
check every current node, I want to see if its
2891.52 -> value, so if current dot Val, if that is equal
to my target. And if it's equal to my target,
2897.2 -> then I can just return true cuz I found the thing
I'm looking for. What I want to do is return false
2902.88 -> only after the while loop, right? It's important
that I return false after the while loop.
2908.24 -> Because only after you check every single node of
the linked lists, can you actually confirm that,
2913.76 -> hey, the target value is not within the
link lists, what you don't want to do
2919.28 -> is write a like if return true, and then else
return false, right, this code would be wrong.
2926.16 -> Because let's say you don't find the target
value in the very first note of the linked list,
2931.2 -> then you would just incorrectly return false
without even looking at the rest of the linkless.
2936.16 -> So none of that we at least want your code
like this. So let's give it a test run,
2940.64 -> see what we get. Nice. And there we have our
iterative solution for this linkless find
2945.52 -> problem. Let me quickly show you the recursive
version of this, it's going to be very similar.
2951.52 -> So in the approach video, if you haven't
watched the approach video recommend you do.
2954.8 -> But in the approach video, we mentioned that
we can solve this recursively by just using
2959.28 -> two base cases, right? I'll start with the base
case if my head is equal to null, all right, so
2964.4 -> that kind of represents the end of my linkless or
also just the empty link lists. So if head is no,
2970.88 -> I can't possibly find the target within
an empty link list. So just return false.
2976.8 -> Now I need my other base case, right? paid my like
affirmative base case. So if head is not know that
2982.08 -> I can look inside of head and I can check if head
dot val is equal to my target, and I've just found
2987.36 -> the thing I'm looking for so just return true. So
two base cases here, right? One affirmative and
2992.4 -> then one that returns false. But let's say neither
of these are true, right? So my head is not no
2998.88 -> and my head value is not equal to my target,
well, then I need to check the rest of the
3004 -> link list. So here's where I bring in recursion.
And I check the next note. So linkless fine of
3009.36 -> head dot next, and you can pass along the same
exact target. So this is going to tell me,
3015.36 -> alright is the target found in the next notable
and glass or in the remainder of the link lists.
3021.2 -> And I know that this call is going to
return a boolean piece of data, right,
3024.56 -> either true or false. I just want to pass that up.
So this should be good to go pretty concise code,
3032.8 -> give that a shot. Cool. And there
we have a solution that's recursive.
3036.48 -> For this problem. Do you bear in mind when it
comes to the comparison of the complexities?
3041.44 -> Technically, we would prefer the iterative
version, right? They both have linear time.
3046.88 -> But the iterative version has constant space,
right? I'm just using like a current variable.
3052.4 -> Whereas my recursive code uses a linear amount of
space because of the call stack. That being said,
3057.76 -> what I want you to do is practice both of these
solutions. And I'll catch you in the next problem.
3063.76 -> Hey, programmers, Alan here, right? Now I want to
go over the approach we can use for this get node
3068.24 -> value problem. So in this problem, we're going to
take in a linkless. And what we want to do is also
3073.36 -> accept an index as input, what we want to do is
really return the nodes value at that given index,
3080.16 -> and we will start counting our indices at zero.
In other words, we'll consider the head of our
3084 -> linked list as having index zero. So for this
particular example, if I asked you for index two
3089.6 -> of this linked list, you should return the value
of the C note right? So just return the value
3095.44 -> c. And of course, that could be giving you any
particular index as input. So what this question
3101.68 -> asks is pretty straightforward. But how can we
go about solving this one. And so what we can do
3106.24 -> here is a basic counting algorithm. So we know we
want to return the nodes value, who has index to,
3112.64 -> so when we initialize our current pointer to be
the head of the linked list, we'll initialize
3117.2 -> our count to zero, then from here, it's just our
classic logic, right? I know I can set current
3123.04 -> equal to current dot next. And when I do that,
I'll also increments might count. So now count
3128.08 -> is one. Basically, I have tracked the index
of my current node that I'm iterating through
3133.68 -> next iteration when current goes to see,
and of course, I increment my count to two.
3138.08 -> At this point, I can see that my target index and
my count are equal. And so I can just return the
3143.28 -> value within that particular node. But think about
the strategy. It's pretty straightforward in that
3148.64 -> if n is the number of nodes, the time complexity
is simply O of n, right? Because in the worst
3153.44 -> case, we just have to traverse through the
entire linked lists. We can also say that
3157.28 -> the space complexity for this is constant, because
we're just tracking some simple number variables.
3162.96 -> So that's how you can solve this one irritably.
How can you also think of this one recursively,
3166.72 -> though, so let's reframe our point of view here,
let's say that we were forced to solve this one
3171.44 -> recursively. And we know we still want to find
the value at index two. And when I make a call,
3176.8 -> I know that the top level caller is going to pass
along the head of the linked list, so the a node,
3181.12 -> and also their target index of two, I can use my
classic recursive linkless traversal algorithm. So
3187.76 -> I make a recursive call on my next node. When
I make the recursive call on the next node,
3192.24 -> what I should also do is pass along the index, but
decrease it by one. So now I'm able to see that,
3198.08 -> hey, this current note of B has index one. And if
I keep doing this next iteration, I call upon my
3204.96 -> next note of C, and I also decrement, my index
down to zero. Once my index is at zero, that
3211.52 -> basically means that I want to return this very
node, right. So if index is equals zero, we'll
3216.88 -> return no dot value, that would be our base case.
And once we return that value, I know that I'm
3222.64 -> going to return back up the stack. So the c value
returns to its color, and so on and so forth.
3229.44 -> Very classic recursive code. So this
looks like a nice recursive algorithm,
3234 -> we analyze the complexity of this, we're going
to see that the time complexity is still in here.
3238.4 -> And the space complexity is actually also linear
here, here, we incur a lot more space complexity,
3243.6 -> because we're going to be storing every call upon
the call stack. So what I want you to do is on
3248.88 -> your own, try to give it a shot, implement
both the recursive and iterative solutions
3253.36 -> for this problem. And if you get stuck,
I'll catch you in the walkthrough videos.
3259.04 -> Hey, programmers, welcome back. Right now I want
to go over a JavaScript solution you can use for
3262.96 -> this get node value problem. So hopefully,
you already watched the approach video,
3268.08 -> if not highly recommend you do that. And we'll
start by implementing maybe that recursive
3273.12 -> strategy off the bat. So I'm going to need two
base cases here, like we said in the approach,
3278.24 -> and one of them typically is always going to be
if our head is equal to null, that means I've hit
3284 -> the end of my linked list or I have an empty
linkless. And what I should do is just return
3289.76 -> know that we'll actually cover a few scenarios.
If I look at the examples here. Sometimes we may
3297.2 -> actually get past a very, very large and Next. So
notice here, they're asking for the value at index
3302.96 -> seven. But the link list only has four different
nodes, that means the index of the last node D
3309.76 -> would be three, right? 0123. So if ever our target
index is out of range, then we should just return
3317.44 -> null. And so this should help me satisfy that,
because I'm going to return no, once I fall off
3323.2 -> the edge of the link list. Nice. We're gonna need
another base case, what if we actually find the
3329.92 -> particular node that we need to return its value
for. So in over time, I'm going to decrement my
3335.36 -> index like we set in the approach. So I can check
if my index is equal to zero, then simply return
3343.76 -> this current node, the current node would be
head, dot Val, right, returning its value.
3348.96 -> Nice. So bear in mind, we're counting
down here. So in my recursive code,
3352.4 -> I need to call my function, get node value,
pass along the next node of the link lists,
3359.04 -> and then pass along index minus one. And
I know that this call is going to return
3365.04 -> the value of the node at the given index. So I
should just return whatever that comes back. As
3371.52 -> I do a quick sanity check here. Bear in mind,
we're counting downwards. So for like this
3375.52 -> example, example, 00, we know that A is going
to have an index of two, right technically,
3381.44 -> because we're going downward. And when I make the
call for B, it's going to receive index one, when
3386.56 -> I call on C, C is going to receive index zero,
which means I should just returned that back up
3391.92 -> the stack. So kind of counting downwards here in
the reverse. But this should be a nice solution.
3398.64 -> Let's give us a test run. Bear in mind, this
solution has a linear time complexity and also a
3404.32 -> linear space complexity, we can actually cut down
on the space if we write the iterative version.
3410.48 -> So I'll show you that right now. So the intro
translation, you should be very familiar with
3416 -> probably wondering, why are we doing such simple
problems? Well, it's about to get more difficult,
3419.36 -> right? To me, it's all about the foundations.
So our classic strategy is for iterations, set
3425.04 -> your current variable to be the head node, right,
I'll just lay out the classic traversal. So while
3431.28 -> my current is not equal to no, then keep on going
to progress to the next node in the sequence,
3439.04 -> what I should do is set current equal to current
dot next. And now I need to work in the problem
3445.136 -> specific logic here, right? I know I want to
return the node at the given index. And for
3450.56 -> these iterative patterns, all counts upwards.
So I'll set some count variable equal to zero,
3455.6 -> just like this. And whenever I progress
to the next node of the linkless,
3460.453 -> all set count plus equals one. So I'm counting
upward. So when I get to some point when my count
3468.24 -> is equal to my target index, and I can just return
this node, right, so I can return this nodes
3475.52 -> value. So again, we're counting upward in the
air diversion, whereas in the recursive version,
3480.8 -> be counted downward. Nice. Let's go ahead and run
this code. There was one thing that probably won't
3489.12 -> pass, but we'll give it a go. See what happens.
So I'm getting an error here, get node value
3495.68 -> has already been declared, because of course, I
have it defined twice. So we'll try that again,
3500.8 -> can't read declare your const variables. So
we'll run it. And we're failing test 02, which is
3508.64 -> the test where our index or a target
index is too large. So here's 02.
3513.36 -> So we should have our function return null. If
we can't find the node at the specified index,
3518.72 -> right now we're returning undefined, which is
happening because this while loop is actually
3524.48 -> ending, right, we're going to hit the very, very
tail of our link lists. And so our while loops
3529.76 -> over and we're just going to hit line 16. When
we fall off the edge of our function evaluation,
3535.12 -> we're just going to by default, return undefined.
So to fix this, it's quite straightforward,
3539.68 -> just by default, return null. And that should
satisfy that scenario. Let's give it a run there.
3547.84 -> Cool. And there, we have an iterative solution.
So for this iterative solution, it has a linear
3554 -> time complexity, just like the recursion, but
it has a better space complexity right here,
3558.56 -> we consider this constant space, because we
only use a handful of variables, like current
3563.6 -> and count. That being said, what I want you to
do is practice both of these implementations,
3567.68 -> because in the next few problems, it's going to
get a little more involved. I'll see you there.
3575.12 -> Hey, programmers, welcome back. Right now let's
go over an approach we can use for this reverse
3578.88 -> list problem. So in this problem, we're going
to take in a linked list that's input. What
3583.76 -> we want to do here is actually reverse the order
of the nodes in this link lists. So if our input
3588.96 -> list contains the values ABCD in place, meaning we
want to mutate the existing linked list in place,
3595.12 -> we want to actually change the order to DC ba just
ending up with the link list. in reverse order.
3602.24 -> In this function, what we should do is also return
the new head of the linked list. So technically,
3606.56 -> your function for this input should return the D
node. So let's come up with a strategy we can use
3611.76 -> to solve this one. When it comes to the tools we
can use for a linked list, we know more or less,
3616.96 -> we always have to iterate or traverse through
the entire link lists. And we know that that
3621.92 -> requires at least one pointer. Typically, we
call it current. The trick here is actually use
3627.76 -> multiple variables. So let's say I began my
classic current pointer pointing at the head
3633.12 -> of the link lists. What I'll also need is to
track the previous node I visited at the start,
3638.96 -> because I haven't visited any other nodes, we
can make this previous pointer point to know.
3645.28 -> And we know this entire time, if I have access
to current, I also have access to the next node
3650.64 -> in the list right by just accessing current
dot next, we're just going to label that as
3655.92 -> a temporary variable here. And we'll call
it next. And you'll see why in a little bit.
3660.4 -> So I know I need to have the long term effect of
just reversing all of the next pointers in this
3665.12 -> link list. In other words, I need to make a point
to know. And so what I can do is literally just
3671.2 -> set current dot next, in other words, setting
the arrow to point to previous ending up with
3676.8 -> this. Now it should be abundantly clear why
we saved the B node with that next variable,
3682.56 -> because once we reroute current dot next to point
to No, we would lose access if we didn't have
3688.24 -> that next variable. So what I can do now is
shift my point of view, I can set my current
3693.2 -> to be the next and set my previous to be the
old current just shifting my point of view,
3698.32 -> like this. And now I can set current dot next
to be the previous node once again, rerouting
3703.28 -> this pointer. And this process continues.
As we get toward the end of the link list,
3708.4 -> we have to also remember is technically since D
is the old tail of the linkless. This entire time,
3714.24 -> it actually did have a next pointer
just happened to point to know.
3719.84 -> And so at this point, I can actually continue
my general algorithm right, I still set
3724.24 -> current dot next to my previous rerouting this
pointer. And I can actually continue one more
3729.52 -> iteration. If I set current to be the next, it's
now the case that current is actually at null,
3735.68 -> which means we hit the end of our linked list
and we can stop our algorithm. If we look at
3741.04 -> the current state of our linked lists, it
is in reverse order, right D points to see
3745.2 -> points to B points to a points to null. So things
are good to go there. And if I wanted to return
3750 -> the new head of the link lists, I can simply
return the final value of the previous variable.
3756.32 -> So that actually works out pretty elegant.
If we do the analysis for this algorithm,
3760.64 -> if we implement this in an iterative way, and we
say n is the number of nodes, we know that the
3764.96 -> runtime is just going to be O of n, really just
traversing through the entire linked list once
3771.28 -> we can say that the space complexity is constant,
because we only need a fixed number of variables.
3775.84 -> So overall, this is a maximum efficient algorithm
to reverse a linked list. When we go on to the
3781.6 -> code walkthrough for this, I'll actually show you
how to implement this iteratively and recursively.
3785.92 -> Bearing in mind that the recursive would actually
suffer a slightly worse space complexity. But
3791.12 -> before we get there, try to give this a shot
on your own implement this if you get stuck,
3794.56 -> I'll catch you in the walkthrough video. See
you there. Hey, programmers, welcome back.
3800.32 -> Right now I want to go over a JavaScript solution
we can use for this reverse list problem.
3804.64 -> So hopefully already watched the approach video,
if not, I highly recommend it, because we're gonna
3808.56 -> implement that strategy pretty closely. So I'll
start with the iterative version here. And we
3813.68 -> know we just need to lay down at least initially,
our classic linkless traversal is just going to
3818.96 -> keep my current variable initialize that to head
and loop while my current is not equal to no.
3825.52 -> And I know that the basic code would always be set
current equal to current dot next, that would just
3830.8 -> move sequentially through the linked lists. But
we need to work in a few other variables, right.
3836.8 -> So the key here is to have some variable, we'll
call it previous and to initialize it equal to
3842.16 -> null. And if we were wondering why null is a great
default value for this previous, just think about
3847.84 -> what needs to happen on the very, very first
iteration of our while loop. So we know that
3851.76 -> our current is going to be a, and in the long run,
we know A's next needs to actually point to No,
3859.04 -> right because he needs to become the tail.
So if we initialize previous with no,
3863.36 -> on the first iteration, we can immediately just
say current dot next, equals previous right,
3869.12 -> that would actually have that arrow
point to null, which is good to go.
3874.96 -> But then at this point, we need to make sure
that we have some proper references here.
3879.52 -> So before we just reassign current dot next,
if we just overrode it, willy nilly, then we
3884.88 -> would lose access to whatever the actual next note
sequentially was. So I'll save that to a variable.
3890.4 -> I'll say maybe const next, equals current dot
next, and then after I override it, I can still
3897.68 -> make progress to the next node of the linked
lists. by simply setting current equal to next,
3903.92 -> awesome. So that's looking pretty good. And not
only do I need to progress current, but previous
3910.4 -> should now also point to current shifting my full
point of view. So some pretty tricky logic over
3917.76 -> here. Let's go ahead and maybe analyze a little
bit closer, what it's doing, please mask er here.
3924.24 -> So let's say we had a link list
that looked like this A points to B
3928.56 -> points to see, we know we have initially current
over here, right, so current is pointing to a,
3936.16 -> we know that when I save that next variable, it's
going to point to this B over here. So I'll save
3941.76 -> that. And technically at the very start, we
initialize previous to be null. So I'll just
3946.4 -> use like capital n represent null. And I know
previous is going to point to that like this.
3952.72 -> Awesome. So on the first iteration, we
have all these variable setup and I set
3957.52 -> current dot next equal to previous current dot
next is represented by this arrow. So when I say
3964 -> current dot next to be previous, it has this
visual representation, right, just setting it
3970.48 -> the opposite direction, once I do, they would
actually lose this arrow. And now you can probably
3975.52 -> see why we saved next for B, right, that way, you
don't lose access to the rest of the link list.
3982.24 -> Cool. At this point, I can set some variables,
right, I can make previous, the current,
3988.16 -> so I'll set it like this, then I also set
current to the next. So basically just shift over
3994.08 -> the point of view. And if you look at the state
of my drawing, now, things are actually perfectly
3998.72 -> aligned. For the next iteration, I would just set
current next to be previous once again, and so on
4005.04 -> and so forth all the way through the very end of
the link list. And like we said in the approach,
4011.84 -> once we actually end when current is equal to
null, you exit the while loop, and previous would
4017.04 -> actually contain the new head of the link list.
So I'm just going to return previous over here,
4023.44 -> it doesn't make sense that previous would be the
new head of the link list. Because after exit the
4027.76 -> while loop, I know previous is going to be the
original tail, right? If I'm reversing the tail
4032.56 -> becomes a head, and vice versa. Cool. So really
just a spin off of our classic linkless traversal,
4038.8 -> I will tell you that the logic here can get pretty
tricky, especially with these temporary variables.
4043.2 -> So we'll give it a test run, see what we get.
And hopefully, we'll have this nice O of n
4047.84 -> runtime o of one space solution. Awesome. There we
have it. And so what I'll also do now is show you
4053.92 -> the recursive version, it will have a slightly
worse space complexity, although the code is
4061.04 -> noticeably more concise. So I think it's still
worth practicing. So really, we're just going
4065.2 -> to translate the same premise into its recursive
version, right. So I'm going to still need like
4070.96 -> access to two variables, or two pointers. And the
way I establish that recursively is by using a
4076.4 -> default argument here. So I'll set previous equal
to null. So if you're unfamiliar in JavaScript,
4082.48 -> this is how you just do a default argument. Right.
So if someone does not pass in a second argument,
4087.6 -> when they call reverse list, by default,
it's going to be set to null. And I can
4091.76 -> start with the classic base case, right? If head
is null, then I've hit the end of my linked list.
4097.2 -> And what I can do is actually just returned
previous for the same reason I returned previous
4101.76 -> over here, right previous would actually be
the new tail. And when it comes to actually
4106.72 -> writing the recursive code, I'm just going
to try my best to translate all of these
4110 -> iterative patterns into their recursive analogues.
So I'm going to save a reference to the head next,
4117.68 -> just a temporary variable. Because if I override
it by saying head dot next equals previous,
4123.44 -> I would lose access to it otherwise. So now
I at least have a way to call recursively
4128.4 -> and traverse through the rest of the link list.
So passing next, as the new head and pass in
4135.76 -> head as the new previous, really just
shifting that point of view, once again,
4141.68 -> I think about the return value for verse
list, I know it's going to return a node,
4146.32 -> right, it's going to return hopefully, the new
head of the linkless. So I just want to pass up
4150.72 -> that return value, do stay aware in this problem,
they say your function should return the new head
4156.8 -> of the reverse link list. And this should
actually satisfy that. So we'll give this a run.
4164.72 -> Nice. And here we have a O of n time
recursive solution that is also O of n space,
4171.12 -> right? So apples to apples comparison, if
you want it to get the most efficiency,
4174.88 -> you should prefer the iterative version.
That being said, I still think there's a
4178.24 -> nice value to practicing both of these. And this
is actually a pretty common interview problem.
4183.68 -> So make sure you have this down pat. Before we
hop into the next problem. I'll see you there.
4190.96 -> Hey programmers, Alvin here, right now I want to
go over the approach we can use for the Zipperless
4195.36 -> problem. So in this problem, we're going to take
in two linkless, whatever Want to do is zipper
4200.8 -> these two lists together. In other words, I need
to in place, reassign all of these next pointers
4206 -> such that we alternate between the nodes of list
one and list two. And also looks like we should
4211.76 -> always start with the first note of list one. And
then from that point on simply alternate. That
4217.52 -> being said, let's take a look at another example.
We don't have many assumptions we can use when it
4222.16 -> comes to the length of both of our lists, except
that we know that each list is actually non empty.
4228.08 -> But besides that, what if one of my lists was
longer than the other? Well, then what I want
4232.4 -> to do is alternate as much as I can, and then
just terminate the link lists with the remaining
4238.64 -> nodes. Soon as I alternate with AQ br, at which
point I don't have any more nodes in the list too.
4245.36 -> So I just take all of the remaining nodes
of list one and add them to the very end.
4250.08 -> And so we'll want to keep that edge case in mind
when we come up with a strategy for this one.
4254.48 -> So where do we even start with a problem like
this? Well, you should be familiar with our core
4259.12 -> linkless pattern, right? We just know how to
traverse sequentially through a link lists.
4263.76 -> And so what I can do is actually maintain
two pointers at a time right? One for list
4268.08 -> one and another for list two. So let's say
we started stepping through this example.
4273.04 -> I know I'm past both of these head nodes, head one
and head two respectively. And then from there,
4278.56 -> I can set up some respective current pointers.
And so given in the examples, we always want
4283.36 -> to start with the head node of list one. So I'm
just going to start that down here. And what I'll
4290.08 -> need to do is also track the tail of my output
list, right? Although we're just reassigning
4296.56 -> all of our pointers in place, we're going to
need a reference. That way, we can figure out
4301.36 -> how we can add new nodes to our current output,
we'll say. And since I already begin my chain with
4308.88 -> the first node of list one, then I need
to be sure that I actually progress
4313.6 -> current one. And so current one should really be
pointing at this B node. And so now that I have
4319.12 -> at least a starting node, how can I come up with
a general algorithm here? Well, if you want to
4324.24 -> establish a simple alternating pattern, then what
you can do is just use a counter variable haven't
4329.52 -> started zero. And then based on whether or not
the count is even or odd, that would tell you from
4335.12 -> which list you should take your next node. And so
since I already began with a node from list one,
4340.8 -> what I should do is whenever my count is even,
I'm going to grab a node from lists to when count
4346.56 -> is odd, I'm going to grab a node from list one.
So right now count is 00 is technically an even
4352.4 -> number. And so I'm going to take my next node from
list two. So I look at my current two pointer,
4358.32 -> and it tells me I should just take that cue
node and add it as the next of my tail. And
4364.72 -> so now that I've consumed a node from list two, I
need to be sure I progress current to to its next,
4370.32 -> just like this. And I also need to make progress
on some other pointers here, I need to progress
4374.88 -> my tail also to its next, that way, I can get
set up for the next iteration of the algorithm.
4381.2 -> At this point, I need to increment my count by
one. So now count is one. Since my count is odd,
4386.88 -> I should take a node from list one. So I look at
my current one pointer, and I add b to the tail,
4393.2 -> just like this. And I make progress on all of
my variables, right. So I'm going to progress
4398.48 -> current one, I'm going to progress my tail
and increment my count to two. Since it's even
4404.48 -> now I should take a note from list two. So I take
my AR from current two. And when I set current two
4411.68 -> 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,
4417.36 -> and then I increment my count. So now my count
is three. And now I have an important scenario,
4422.64 -> it looks like I've exhausted all of the nodes
in list two, we spoke about this scenario,
4428.48 -> right? Whenever we finish all of the nodes
of one of our lists, we should just terminate
4433.28 -> our output with all the remaining nodes
of our other list the non empty list.
4438.96 -> And so at this point, what I can
do is just take my current one,
4443.68 -> basically this C chain and everything after it,
and just put it after the tail in my output,
4450.72 -> just like this. And of course, I want to complete
the connection over here. And this would actually
4455.52 -> be the correct output. And so overall strategy
was to maintain pointers to both of our respective
4461.28 -> link lists, and maintain accounts, right,
depending on whether the count is even or odd,
4466.16 -> then that'll tell me from which list I should
take my next node. And along with that, we also
4471.36 -> need to maintain some tail pointer we can use. So
we can actually build up the linked list output.
4477.92 -> Let's talk about the complexity of this one. Since
we have two linked lists as input to this problem,
4484.08 -> we should probably use two terms to describe
its complexity. So if I say n is the length
4489.2 -> of list one, and I say m is the length of
list two that I can say the time complexity
4494.32 -> is the minimum between n and m. Recall that
when we just step through this algorithm,
4499.68 -> we really only needed as many iterations as the
shorter linkless. Recall the algorithm we just
4506.48 -> traced through. Now once we hit the end of one
of our link lists, we know we just finished the
4511.52 -> algorithm by taking the remaining nodes of the
other list and just tack it on to the end. And
4516.48 -> that finishing step only takes an O of one time,
surely, as soon as one of our linkless runs out,
4521.76 -> which will always be in general, the shorter one,
then I can just finish my algorithm, I actually
4526.32 -> don't have to iterate fully through both of them.
And I would still consider this technically, you
4530.56 -> know, some form of a linear runtime. For the space
complexity, you can see how the space here is just
4537.04 -> constant, right? We're not actually creating any
new nodes, we're simply rerouting all of these
4542.16 -> next pointers. And in terms of our variables, we
only use a fixed number of them. And so overall,
4547.44 -> this seems like a reasonable strategy, what I want
you to do is try to code up this one on your own,
4551.6 -> it's going to be some really interesting
code, a new pattern for us that is,
4554.88 -> and if you get stuck, I'll catch you in
the walkthrough videos. See you there.
4561.36 -> Hey, programmers, Alan here, right now I want
to go over a JavaScript solution for this
4565.68 -> Zipperless problem. So we'll jump right in,
hopefully watch the approach video. And we'll
4569.92 -> start with an iterative version of this, the
way we're going to attack this one is by doing
4574.32 -> our classic linkless traversal. But do it twice
over for a head one and head two simultaneously,
4580.56 -> really. So I'll set my let current one, start
at head one. And I'll also set let current to
4588.4 -> the start at head two. And I'm going to need
my main loop just to iterate through the
4594.24 -> linkless. Second check, while current one
is not no. And current two is not at all.
4602.88 -> So notice, as soon as one of my linkless hits
its end, this loop would actually stop, right?
4609.52 -> Cool, we want to be sure to do is set up also a
way to create the output. So look at the prompt,
4616.16 -> we always start with the first node of
list one. So in this particular example,
4622.72 -> I'm zippering, ABC and XYZ, I always start
with the a here. And we're going to use
4627.76 -> that to get the ball rolling on my resulting
list, we're not going to create any new nodes.
4632.72 -> But we do have to rewire all of these next
pointers. So what I'll say is maybe, let's
4640.16 -> say head over here, and this will be the head
of our output, because I know I need to return
4644 -> that by the end, something like that, I'm going
to start head really as head one, technically,
4653.84 -> and then current one will actually have to start
one after that, like we said in the approach.
4658.32 -> So I'll set current one equal to we'll say,
head dot next, that'll be a good starting
4666.48 -> point from there. And in addition to having this
a head pointer, that's because I want to return,
4672 -> you know, the new head of billing class, which
I guess would be the same as head one as I think
4676.24 -> of it. So maybe we don't need this variable. But
we do need is a pointer that we can append after,
4682.32 -> right. So I'm going to say left tail, I think
as a matter of fact, when I set tail equal to
4689.28 -> head one, say no head, one's going to be
the first note in my output. And over time,
4695.36 -> I need to add things after the tail building up
my resulting list. So that's looking pretty good.
4701.92 -> Now we'll go ahead and increment our counter,
add that into the mix here. So we'll say
4707.36 -> let count beginning at zero. And dependent on
whether or not our count is even or odd, that can
4715.2 -> tell me whether I should take a node from list one
or list two. So I think we're ready to hop into
4721.6 -> our main code over here. I know I should end any
particular iteration by of course, incrementing,
4728.24 -> the count, right? Count plus equals one, I'm just
going to put that down there. So I don't forget.
4733.76 -> And I will start by checking the parody of that
count, right whether or not it's even or odd,
4738.08 -> so I'll simply check if count mod two is
equal to zero, right, so that means it's even
4746.24 -> an else it's odd. So bear in mind, I started my
output list with a note from head one from list
4752.4 -> one. And initially, I start my count equal
to zero. So I guess when my count is zero,
4757.68 -> I'll take something from list two. So what I can
do is take whatever current two is pointing at,
4764.08 -> so current two, and I want to make that the next
of the tail, right tail is helping me build the
4770.88 -> output. So simply tail dot next equals current
to nice. Then from there, since I just used up
4779.36 -> something from list to I need to progress that so
current to equals current to dot next. And I know
4787.28 -> that this code over here, when it's odd, it's
going to be symmetric, just for current one.
4795.2 -> And in addition to that, we need to make sure that
we also move our tail pointer that's going gonna
4800 -> happen in either scenario. So I can put that
mutual code over here, I think I'll say tail
4805.52 -> equal tail dot next. Nice. So this should help me
construct my alternating pattern. But we have to
4813.52 -> worry about is based on my while loop, this while
loop is going to terminate or end, as soon as one
4818.64 -> of my current pointers hits null. And it could
be the case that only one of them is null, and
4824.16 -> the other one is still pointing to some data. And
like we said, in the approach, what we should do
4828.56 -> 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
4835.36 -> check here, right? If, let's say, current one
foot still has stuff, so it's not equal to know
4842.08 -> that I can just take that stuff and add it to
the tail. So tail dot next equals current one.
4852.16 -> And symmetric for current two, of course. So
I'd look at the prompt over here, we're thinking
4859.6 -> about a scenario like this one right here, we know
that current one is way longer than current two,
4865.6 -> or list one is longer than list two. And so by the
time we get to the end of list two, we know that
4873.04 -> roughly we're going to be at about this C node or
this D node in list one, we just want to take all
4877.84 -> those remaining elements looks like D, and add
it to the end of that list. Notice I just end in
4883.28 -> DEF. Cool, and we just need to check both
sides of that. Awesome, I think at this point,
4888.08 -> let's give this a nice test run. Gonna always
debug it together. It's not too long of some code,
4893.84 -> but it does have some interesting patterns.
Awesome. Here, we have a nice iterative solution
4898.24 -> for Zipperless. For this code, we're looking
at linear runtime, and constant space. And so
4905.44 -> I think what we'll do is, let me also show
you how you could solve this one recursively.
4909.84 -> It's very similar and strategy, somewhat shorter
code. I'll leave it to you whether or not you
4915.76 -> think it's more simple or not. We will have to
concede, though, that for any recursive code,
4921.52 -> especially for this one, we're going to have some
additional stack space used. So we would have
4926.88 -> a linear space for recursion as well. So
I'm going to do my best to translate these
4931.12 -> patterns. So I know I should stop my recursion
will say if head one is no, and head two is no.
4941.04 -> So that's very similar to what we just said
in our iterative version. And if there are no,
4946.32 -> then you kind of at the end, you can just
return null. What I have to be sure I do is
4952.24 -> for my function needs to return like the new head
of the linkless. And so I'll just have some base
4957.44 -> case here, where I return null is basically a
linked list contains like many sub lists, right?
4964.4 -> What you should be doing as you solve linkless
problems. Recursively is, if you think of let's
4970.16 -> say this as a linked list, going from A through
Z, then going from x to z is also linked lists
4977.44 -> going from B to Z is also a linked list. So
that's how I kind of break down my problem size.
4982.96 -> So if they're both null, then return null. But
what if only one of them isn't? All right. So what
4987.52 -> if head one is no. All right? And that would mean
if head one is the only one, that's all that means
4995.2 -> had to have some stuff, well then just return
the remainder of had to make that symmetric for
5001.76 -> the other side, right? So we've had two is nil.
And had one isn't, then just return the remainder
5005.92 -> have had one. And what this base case or these
base cases will let me do is accomplish some
5012.08 -> logic, just like this, right? How can I take
all of the leftover nodes in the case of one
5018.96 -> of my lists running out and just tack it on to
the end? Right, if one of my pointers runs out,
5024.24 -> I'm just gonna return the other pointer. Cool,
which would be the leftover chain. Now I need my
5030.24 -> recursive code. So there are a few ways you can
write this. Instead of using the modular trick and
5036.16 -> checking for even or odd, what I should be able to
do is take two notes at a time here. So let's say
5042.16 -> I know I need to make my head head one, really. So
I'm going to return head one, I think at the end,
5049.76 -> and I need to make head one dot next
point two, whatever had to is, right.
5057.68 -> And as soon as I do that, I would actually
lose access to the original head one next,
5061.2 -> so I should have saved that. So I'll
say maybe const. Next one equals had one
5066.8 -> dot next before I overwrite it. And I guess why
not. While we're here we'll also do the same for
5071.36 -> next to pretty common thing we have to do for a
linkless problems right before you overwrite a
5075.6 -> pointer, maybe save it in case you need it still.
So I'm making head one next point to head to
5082.56 -> and then from there. I know I need to
call recursively zipper list on next one.
5089.36 -> And also, next to it should be right. And then
from here, I just chained head one to two. I
5098.08 -> know Zipperless is going to return In the head of
the remaining linkless, I just need to chain that
5105.36 -> to head to so had to dot next equals that return
value, because again, I'm going to return a
5110.96 -> node from this recursive call. So this code is
looking pretty good. Let's go ahead and test it,
5118.24 -> it is quite a bit shorter. So we're getting error
Zipperless is not defined. Because I s here,
5125.2 -> that's on me. Give that a go again. little
typo there. Nice. And here, we have a nice
5133.52 -> recursive solution for this. And so just
to make sure we're on the same page here,
5139.44 -> maybe it's worth stepping through at least one
iteration together. And so let's say I had these
5143.6 -> lists had ABC and XYZ, trace through at least
one stack frame of this. So ABC, and then x,
5152.08 -> y, z. Alright, so I know in the context of
my pointers, I have h1 over here, right,
5160.24 -> that's going to be head one. They also have head
two, of course, so h2 over here. And what I do is,
5167.44 -> I'm not hitting the base cases for this, because
I have two nodes. And so we save some pointers to
5172.4 -> their next. So nothing fancy here, I have next
one over here, I have next to over here. And in
5180 -> the core logic of actually alternating, what I do
is I take head ones dot next and point it to head
5186.88 -> to. So I don't want to just kind of merge them
together in line over here. So kind of separately,
5192.16 -> although you know, I'm not creating new
nodes would look like this head one is a,
5196.72 -> I said it's next to x. So that already looks good
to go. And then from there, I set head twos next
5204 -> to whatever the recursive call is, when I pass
along, next one next to so at this point, I can
5209.52 -> kind of ignore these. Right? So I'll take out just
this a node. And now h one, or head one points to
5219.28 -> be the same thing over here. H two points to y.
And let's say we step through this iteration,
5225.68 -> well, same thing. I just take head one,
and I know I'm going to return head one,
5230.96 -> right? So eventually it's going to return over
here. It's going to say B points to why, right?
5237.04 -> Because head one is B h two is wine head one
that next equals head two, and that's good to go.
Source: https://www.youtube.com/watch?v=Hj_rA0dhr2I