So when we come up with our first test case, we call it our best case test case because we want it
to really help us derive all of the correct insights so that we can get to the correct solution in order
for us to get all the right insights, we need to make sure we're looking at the total problem space,
which means that anything that might sway our logic is going to be captured in this test case or at
the very least, we're going to try.
So when I say that, when you look at this question, your intuition tells you that the most important
thing other than getting all of these less notes into one level, is that the order of the list notes
that get merged together is important.
We care about the order in which the list notes appear in one single, doubly linked list.
When that's the case, really think what are the factors that might affect the order?
You don't have to be certain, but it should be enough that your test case tests it because we need
to use it to actually approach the insights that we need to know in order to come up with a solution.
The first one that jumped to us is that multiple levels might influence this outcome.
So, for example, we know that for sure we can have multiple levels beyond just two.
So here, if we come up with a first doubly linked list and inside we have a child, let's say, at
17 2:00 and this child has its own list.
And then inside of this child, this child has its own list.
We have three levels, so here when we actually start stepping through it and trying to figure out the
correct order to merge these list nodes in, we at least have three levels, which is enough for us
to consider what happens about the order of 10 and 11 compared to seven, eight and nine when these
all get merged into the first level.
So that's one big thing that we can do.
The second is, does multiple children at the same level influence the order or at the very least,
is there a way that we can account for it so it doesn't?
So here we can add another child right here and let's say this one is 12.
So with this, we have multiple children at this level as well, so we know that the 12 13 must come
between the five and the six just by looking at it.
So at the very least, we know that here we have captured enough.
If the 12 and 13 end up anywhere up here in the front, we know we've probably done something wrong.
From here, we need to come up with what the final output of this linked list will look like, and here
we can actually start thinking and getting our gears, turning about what the flow of merging might
be, because we need to be able to do this in person before we even start thinking of a solution.
So we know that for sure we want to merge the seven, eight and nine into the one, two, three.
This 10 and 11 should never come before the seven, eight and nine, because this is a child of the
eight, which is inside of the seven, eight, nine.
So if 10 and 11 ever appears in this list before, seven, eight and nine, we know we've done something
wrong.
But what we can see here is that if we start going from one to two to should not attach the three because
it has a child, we know that the seven is important.
So here we can immediately start writing that we need one, two and then seven.
From seven, does it have a child, it doesn't.
So we know that we can start upending the rest, which is the eight.
Here we can see the eight has a child, so the next value is not going to be nine.
It's going to be the child value, which is 10.
Then we add the 11 because we see that none of these have any children, so we can just slot this right
between the eight and the nine.
And then we have the nine.
Now that we have the nine Wiecek.
What comes after two, it's three, so now we add the three.
Then we add the four and then we add the five, once we've added the five, we see the five as a child,
so we can't possibly add the six from here on, we got to go down.
12 has 13.
None of these have any children, so we know that once 13 is in there, we can append what was originally
at the end of five, which is six.
And now we have our full, doubly linked list, so this is what it flattened into one level looks like.
So now that we have this single link list and we have walked through some of these examples, we have
a general idea of what the merger should look like.
We know that we can merge a level in it doesn't affect the outcome as long as when we advance to the
next list node.
Inside of this merged in child, we account for its children and any children that the remaining list
nodes might have.
It will become much more apparent when we start, actually.
But right now, just from walking through, turning our test case into the correct answer, we've already
kind of seen what this looks like.
Your intuition will help you do this anyways.
But the problem is you have to slow it down and really start thinking about what these steps could mean
and how that order might matter, because from here, it might give you hints towards getting to your
solution.
So what this test case, we also need to account for some null cases.
In this case, we might just account for what happens if we get null as an answer.
Then when this happens, we do want to return null back.
Also, what happens if we receive a single level or a single node?
We can count them as the same thing.
We can just account if we get a single node, which is one level.
We also want to return back as the answer three.
So here we have pretty good test cases to start working on a solution.
Now I do want to challenge you to try and come up with your own logical solution.
All of those techniques and all of the strategies that we learned with single link lists are still applicable
here.
We're still trying to figure out how to traverse from the very head of our linked list onwards to the
next nodes.
It's just that from here we have multiple directions.
We can go, we can go backwards, we can go forwards.
We can also go potentially down if there is a child.
The thing that's important to note is that because we have the new previous property as well as the
child property, we need to think about the appropriate things to do with these pointers.
Let's say we're merging the seven, eight and nine into the two and three.
This means that you need to remember that the Sevan's previous property needs to point to the to the
next property doesn't point to three anymore.
It points to seven, which was its child before.
The child needs to get pointing to null, the nine needs to point to two's previous next value.
Then three is previous value needs to point to the nine as well, so these are all the additional pointers
need to count for.
But remember, the more you sit with the and the more you struggle and fight with it, the more it'll
make sense.
And the more we practice our critical thinking, our critical thinking is going to be the most valuable
tool for us with these interview questions.
Just walking through this step by step and just trying to draw insights about what the logical steps
to do are are going to help you get to the solution.
And remember, with Linklaters questions, it's all about traversal.
It's about traversing one note at a time, trying to figure out, based on the conditions of this note,
having a child, for example, what things do I need to keep track of?
Do I need to advance my notes any further?
Do I need a new pointer?
These are all considerations you have to think about.
All of the tools are there for you.
It's just about putting it together through fighting with the question and thinking about it critically.
So spend some time and really try and think about this question.
I promise you that it's a lot closer than you think.
In the next lesson, I'm going to show it to you.
So I'll see you in the next lesson.