Hi, everyone.
So today we are going to solve this problem partition list.
OK, so the problem statement is very simple.
We will be provided with the linked list.
So input will be a long list and a value of X.
So in this case, if the value of X history now, what is the problem?
So the problem is very simple, but we have to do so.
We have to partition this list in such a way that all the values which are less than X should come before
the values which are greater than X.
OK, so in this case, what will be our output?
So one.
Two and two, so there are these three values are less than three.
OK, so one to two.
So all these three values, they should come before the values, which are greater than three articles,
two, three.
So this is for this history and this is five.
So for three and five, OK.
So this will be my, let's see, less and less values and these are more values.
OK, and what will be our output to our output will be we will make this a linked list.
So one to two, and this is four, three, five.
And then we will append this part.
OK, so this should be our output.
OK, and one thing you cannot change in order, for example, you cannot write like this two to one
or similarly, you cannot write like you cannot start this part three or four or five.
You cannot write like this.
This is wrong because in the end, it is mentioned that we have to preserve the original order.
OK, so what do you mean by preserving the original order so you can see for this coming before?
So in the output force should come before three.
Similarly, three is coming before five.
So in the output, three should come before five.
OK, so this is the meaning of preserving the original order.
OK, so we are preserving the original order of the list.
OK, so this is the question.
So this question is present on little and here it specifies that we have to preserve the original order
of the linked list.
OK, so we will be given a value X and all the nodes whose value are less than they should come before
the nodes whose values are greater than the X..
OK, and this is my order.
So these values are less than X and these values are greater than or equal to X.
OK, so we have to solve this problem and the expected time complexity is basically linear and the expected
space complexities or an OK, so constant space and linear time.
OK, so how we can solve this problem.
So basically what we are trying to do here is so what we will do.
So let's take about example only.
So we have one, four, three, two, five and two.
OK, so this is the example given on the code and the value of X history.
So what I will do.
I will I will separate I will partition this list into two parts.
OK, so I will have less help, less deal and more head and more deals, more deals.
So all the values which are less than X will come in this part.
OK, so this is less than expected and this is go to the next part, OK.
So this is more head.
Basically, the head of the list, and this is Mortell, basically the tail of the linked list and some
less head and less tail.
So what we will do, we will iterate over the linked list.
OK, so we will trade over this link list.
Now, what we will do will compare the value.
So compare one with three.
So one is less than three.
So it will be the part of the left hand side.
OK, and initially all this will be null.
Initially linked list doesn't exist.
So all these are OK now one is less than three.
So we know this will be the part of the left linked list.
So it will one will come here and it will do so.
Less head and less tail.
Both will point towards one initially.
Now we will compare four with three.
OK, so four is good then three.
So it will be the part of the right hand side more.
OK, so four will come here and I will update my more head and more tail, then compare three with three.
OK, so it will come in the right hand side.
Now I have the option, I can write three here or I can write three here since we have to preserve the
original order of the linked list.
So this is wrong and this is right.
OK, so basically what we are doing here is we are inserting at tail position.
OK, so we are starting at tail position now.
After the inserting modulo we will update our model so more tail will come here.
OK, now compare to so obviously two will go in the right and left hand side, so two will come here
and I will update my left bill.
So left till then, compare five.
So five will come here and I will update my Motyl.
OK, now, compared to with three, so two will come here and I will update my left.
Deal.
OK.
Now, when this is over, after reading of the linked list, what we have to do, so this tool will
point towards food.
OK, so basically what we have to do so the next off left bill, it should point towards the more ahead.
OK, and now what we have to do, we have to return the head of the linked list, which will be lifted.
OK, this will be our head of the NewLink list.
OK, so this thing we have to do after my left, after my head and less tail more and more, all these
four variables are ready.
OK, now let's write this code.
And while writing the code, they will be like few cases that we will handle.
OK.
So first of all, I have to create four variables.
OK, so let's head, which is basically nil.
Similarly, Lesterville.
We need less deal, which is.
We need more help, which is Mel.
We need more detail, which is all tunnel.
OK, so all my four babies are ready now.
We have to do we will simply iterate over over the long list.
OK.
So while it is not a questionable.
OK, now I have to decide whether this node will go in the last part or indeed more part.
So if the value of a.
Is less than X, so it will go in the left part now in the left part.
I have to check first if the left have a constitutional.
So we have to initialize our left head.
OK, so we will initialize our left hand and we will also initialize our left.
So they both will be OK and then they'll start.
That means they have already been initialized.
So I have to insert a detailed position.
So we inserted Bill.
So what we have to do, so will some do left in the next?
It's basically a and then we will move the left.
OK, so Lefty Licalsi, or you can also right left Bill Ecoles next of Lefty.
OK, so you can write both now here what we have, what we have done.
So I think you understood this part so initially, so initially left head and left in the boat were
pointing towards Snel.
So first of all, one will come here.
So when one comes, I have to update both left and left elbow will be updated and once the left hand
left, they are not null.
Then I will insert at the tail and then I will update the left.
OK, so this is how it is working and we have to do the same kind of operations with the right part
also.
OK, so in the early part.
What we have to do, so I'm copying this part.
We have to do some minor changes only.
OK, so if the Moorhead.
If the Morehead is null.
So I will update my head and I will update my Mortell.
Similarly, it should be Mortell and it should be Motyl.
OK, now.
What we have to do, so now we have to move ahead.
OK, we are taking over the linked list.
We have a while loop.
OK, so we have this wide loop so far moving ahead.
We have to read this line, OK?
A quiz next of a.
Now, once this Vilo is ready, will both left and right and they are ready.
OK, so both left and both less and more, they are ready.
OK, so let's.
And the more linked list already.
Now, what we have to do, we have to simply append them.
OK, but we cannot simply append them.
For example, let's say if my list is let's say one, two and three, and let's say the value of X is
for.
So in this case, my left hand will point towards one and this will be the scenario.
This will be the left bill and more and more tail, they will be null.
OK, so in this case, what we have to do, we have to simply return the left hand.
OK, we will not do any like a band operation.
We will simply return the left hand.
OK, now that that case can be let's say I have five, six and seven.
So if this is my list and the value of X is four, so in this case my left hand and left in the boat
will be null and.
My head will point towards the fife and my Mortdale will point towards the seven, so in this case,
what we have to return to, in this case our output will be Morad.
OK, in this case, this will be our output now.
And if both the linked list exist, if both less and more likely to exist, then what we have to do,
we will do this operation.
We will append we will do this operation, and then we will return the Lassard, OK?
So we have to handle some cases, so first case.
Left link list exist.
OK, and rattling list does not exist, so basically rated inconsequential.
Now, in this case, we do not have to do any operation which we can simply read on the left hand.
OK, now the elusive.
In the elusive condition, Leaside does not exist.
And right head exist, so basically this is Morad.
OK, more exist.
So Morad is not close to null.
Now, in this case, we can simply return the more head now in the end sport, both less and more exist.
So what we have to do, we have to first up.
And so the next of.
Left Bill less still, basically, this is more Moorhead.
And then we can simply return less head.
OK, now this is the complete completel, so if we will run this court, we will get time limit accelerated.
OK, so let's see.
OK, so this condition is wrong.
Basically, it should be left held, less medicinal and more is not.
Now, if you will, in this court, we will get it accepted.
OK.
So we are getting excited.
Now, let's see, let's try to understand, because as we discussed our time complexities, basically
we are not doing anything else.
Our time complexity is linear and our space complexities.
And then also we are getting the time limit exceeded that.
Now we will try to understand why we are getting family tax related.
OK, so so let's try another our for this input one for three and one.
OK, and the value of Hexis three and we are getting there.
OK, so our linked list is one.
All three and one, OK, so this is our long list, and the value of X is basically three.
OK, so what we have to do.
So initially, my left leg had listed the anal.
Morad Mortell, they are also NDL.
OK, now we will trade over this long list.
OK, so this is the value of a we will compare one with three.
So obviously this will be the part of the last part.
So I will update my less head and less so less head and less still.
OK, so I will update my list, head enlisted and then I will move ahead.
So this is a no, OK.
Now we will compare four with three, so now this time this will be the part of Morsi, so I will update
my more.
So this is no more red and this is more detail and it will move ahead.
So this is a now compared three with one, three with three.
So obviously this will be the part of the motel.
So motel room next is basically a and then I will update Mortell.
So this is Mortell.
Now, compare one with three, so obviously this will be part of left hand side.
So what we will do so left tail I next.
So left tail arrow next.
It's basically and then we are updating our left bill, so left Bill will come here.
OK, and then what we are doing, so we are doing a final part, so in this thing, both left and both
less and more exist.
So we did something like this left arrow next is basically more head.
OK, so we did something like this.
So this is my left bill.
And what we are doing left Bill Arrow next is more ahead.
So Left Arrow next.
Is.
Morad, OK, so this is Morad, and then we are turning the left less head.
OK, so let's say this one, then one is pointing towards this one.
So one is pointing towards this one, then this one is pointing towards the fourth, so one is pointing
towards four.
Then we can see four is pointing towards this tree.
So four is pointing towards this tree, then three is pointing towards one.
So tree is pointing towards left.
So basically this is the left tail of trees pointing towards one and one is pointing towards three.
Four is pointing sorry.
One is pointing towards four, four is pointing towards three trees again pointing towards one and so
on.
OK, so this will go on.
So basically what is happening here is this is a loop.
OK, so this is a cycle in our linked list.
So there is a cycle in our linked list now how to avoid the cycle.
So for avoiding the cycle, we will simply write so.
Now, once our lesson, more are ready, what we have to do, we have to make their next level, OK,
so left till next.
This is Nell.
And simply what we have to do so Mortell do next.
They are all OK.
We have to OK, so we are making them and now our less and more are ready.
Now let's on the cold.
OK, so now our goal is Working Knowledge Summit.
OK, so we are getting ready daym when our input Lesters and the value of Hexis zero and it is showing
there is at at this point.
Now let us try to understand what is the added.
So initially, obviously, less and less still there and obviously more head and more tail, they are
all tunnel, OK, since the list is empty.
So this is our loop.
So I will not go inside the wire loop.
I will reach at this lane.
So at this point, what we are doing next off left tail is null.
OK, and basically left is already null.
So basically what is the meaning of this line?
We are trying to do something like this null arrow next is null.
And basically, this will give us the segmentation fault now to avoid this error, what we can do so
we cannot write like this.
So first we have to check whether the last part existed or not.
OK, so.
We will right here, so if the last part exist, then first make the next point, then make the next
left bill and then return the head.
And similarly, we will do with this.
OK.
We have to right here also.
OK, and similarly, despite.
If the mortarboard exist, make the next null and similarly, if both exist first, make them null and
don't do the operation.
OK, now let's try to it.
OK, so if the list isn't pretty.
We are getting around Daym so we can handle one more case here.
OK, so what will be the case?
We have to end it like here, this is the case, so.
Else, if if both the linked list exist, so if.
Lassard is not close tunnel.
And Morad is not closed, only then only we can do the following operations now in the L'ESPRIT.
So we welcome.
We will reach this line on live in.
Neither the last part exist, neither the mortarboard exist, basically when the list is empty.
So in this case, we cannot handle OK.
Not at summit.
OK, so now our court is 100 percent correct.
OK, so this is the complete quote.
I will share the court with you.
OK, so if you have any doubt in this question, you can ask me, OK, so the time complexity of our
solution is linear and this is complexities or an.
OK, thank you.