Name: How To Solve Algorithms - Adding Linked Lists
Uploaded: 2020-03-28T16:50:42.000Z
Duration: 13 min 50 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

The imperative

remember a while back when I released my last algorithm video and you asked for more and more outgrew been videos and I said Yes, definitely.

Future simple

I'm going to create more algorithm videos for you.

To-infinitive

Well, as you can see, I took a little while to get to that.

And I'm sorry about that, but I promise you that it is definitely worth the wait.

This is the best algorithm video I've made so far.

And in this video, we're gonna take a look at solving a problem that actually is great because it doesn't test your knowledge of remembering a bunch of really contrived algorithms.

But it actually test you at the core of your problem solving skills and a really unique and challenging way.

So without any further ado, let's get started.

Have simplified where I simplified the web for you.

So if you're new around here, make sure you subscribe for more videos of me.

Let's get started by actually looking at the problem that we're gonna be solving today.

And this problem is called add two numbers, which at face value that appears to be incredibly easy.

But I promise you it's much more challenging than it looks.

And essentially what we're given is to non empty, linked list, and what a link list is is essentially.

But each element in the array has a reference to the next element in that array.

So instead of access in it by index, you access it by going from one element to the next element into the next element and so on until you get to the end of the array.

So it's really easy to go sequentially through the array.

So what we have is with these two linked list, and they were just full of non negative numbers imagers, to be exact.

So whole numbers and these whole numbers are actually representing the digits of a full number, and these digits are stored in reverse order inside of the array.

So if you have the number 120 for example, the very first element in the ray would be zero.

The second element in the array would be too, and in the last third element in that array would be one.

It's just that number 1 20 in reverse, which each of the digits taken up their own element inside that wait list.

And the goal of this algorithm is to take the two length list we get and to add them together and then to return another length list, which has the number that adds together, too.

So let's take a quick look at the example that they're showing us down below.

As you can see, we have a link list, which is 243 which is the number 342 because it's in reverse order and we also have the link list 564 which is 465 since it's in reverse order.

As you can see, we're adding those two numbers together to get 807 and what we're doing returned from our function that we create is we want to return that 807 number.

But of course, in reverse order Sogo seven, then zero and then ate so immediately.

Just by looking at this, we can kind of already brainstorm and initial solution to this problem and the way that it works is just by doing normal addition.

You start with the bottom number, which in our case here is the very first element in our raise.

And we add those two almost together to get seven.

As you can see down here, we then go to the next element, which is four and six.

So what we need to do, just like a normal addition as we keep the zero.

So as you can see zero here, we actually carry over that additional one.

So when we get to three and 43 plus 47 plus, that carryover of one gives us the eight for our final output, and that's essentially the initial solution to our problem.

We're gonna run into a bunch of edge cases as we actually solved this problem.

But let's just start coating up our initial solution to see where the edge cases are as we run into them.

So here we have our initial code, and as you can see at the top here we have our class, which is our list.

It's a little bit confusing cause they put function here, but it's really just a class.

And essentially this list note is going to take a value, and that's going to have that value.

And then it's going to have a next value.

And this next is essentially just a pointer that leads to the next element inside this list node.

So every list note will have a next which points to another list node.

Or if it's the very last part of the array, it'll actually just point to nothing.

So Knoll and just to kind of generate how this works.

Imagine you have an array of zero and one.

This would be exactly the same here as having what's called a new list node with a value of zero.

So this list minute, let's just set it to a variable here is going to be just called one.

Such is the first element in our ray, and we're gonna have to here is gonna be equal to a new list node of one, and we want to do is we want to put one dot next is going to equal to.

So essentially, now what we have is we have a link list where the first element here has a value of zero, and it's got a next property which points to two, which has the value of one.

So this is exactly the same as our ray up here, but we actually access E as elements here by using the dot next property, and that's where we're being passed in here.

We have to link list, which we're going to be our two different elements that were adding together.

So it's clear out all this, coach that we have a base value to start with here.

And the first thing we need to do is actually figure out howto loop through our link list that we have and a really easy way to look over a link list is to use a wild for example.

We can say while and we just want to put a value here, we just call it L one, which is our first link list.

So while L one is not equal to know, we want to do everything inside of this loop and then inside of this loop.

We just want to set out one here equal to l one dot next, and it's just going to get the next element inside about one.

And this is going to look through all of the elements of l one.

But we actually want to look through the elements of l one and L two.

And while in the example were shown, they both were the exact same length.

It is possible that l one will be short of a knell to, for example, adding 420 to 25.

Your second moment here, 25 is only gonna be two elements, so it'll actually end first.

So we need to do in here is we did actually put in and or l two is not equal to know.

So what this is going to do is going to look through this wild statement as long as we have elements in either l one or L too.

And we also need to make sure that down here we put l too equal to l two dot next just so we know that our linguist are constantly iterating over themselves.

One thing to know, though, is as I mentioned before, we have potential for one link list to be shorter than the other.

So, for example, if l to a shorter the l two dot Next is gonna be no.

While l one is not going to be no for dot Next.

So we actually need to make sure that we do a check here.

So you want to say If l one is not equal to know, then we can actually call this dot next function on it and we wanted to the exact same thing down here for L too.

It's just essentially make sure that we don't ever accidentally try to access the next element when there is no next element to access.

We're not actually going to run into these no error exceptions anymore.

So now that we're able to actually end our wild loop by implementing on our link list here, the next thing we need to do is get the value from our length list.

As we could stay up here, we have a dot v A l method, which is our value.

So we can just say that we're gonna create a variable called the one which is this l one dot vow and we could do the exact same thing.

We're gonna do this for RV too, so we can just say V two is going to be equal to l two dot bow.

But again, we have a very similar problem.

For example, three digits and two digits.

If l one is equal, not equal to know, then we can actually set here.

V 12 R l one dot value Otherwise, by default, we want to set V 1 to 0 with studios accent thing for V two.