• 15 hours ago
Transcript
00:00The next question we are going to discuss is to check if a link list is a palindrome or not.
00:05What are palindromes? Palindromes are such numbers that look like the front and the back.
00:11Like 1221, 1441, if I wrote CAC, so this is a palindrome.
00:17If I wrote MAAM, this is a palindrome.
00:20If I wrote race car, so race car is a palindrome.
00:24Because the numbers, the strings, all sequences, and the back, we call palindromes.
00:37Now I have to find out if my link list is a palindrome or not.
00:41If my link list looks like one point, two, two point, one, and this is null.
00:48This is a palindrome.
00:50Here I have to return to true.
00:53And if my link list looks like one, three, five.
00:58And then I have to point null.
00:59So here one, three, five, there is no palindrome.
01:02So this is my false case.
01:04Now this is the first question.
01:06The first question is that I will teach many important things.
01:09The first thing that I am going to teach is my slow fast concept.
01:14We will know slowly what is slow fast concept.
01:18We use it in many questions.
01:19We will use slow fast concept.
01:21The first thing that I am going to teach is this concept.
01:25The second thing that I am going to teach is to reverse the half link list.
01:31How do we reverse the half link list?
01:33Or how do we reverse the one third link list?
01:34How do we reverse it?
01:35If there is a question in that way, then we will teach these questions.
01:40So there are many important things that I am going to teach.
01:42So from learning perspective, this is a very important question.
01:45Now there are many multiple ways to check any link list.
01:49The most simplest way is that I am going to store all the elements in an array list.
01:57Or store it in an array.
01:59Then what do I do?
02:00I am going to check whether my array list is forming a palindrome.
02:03Or the elements of my array are forming a palindrome.
02:07This is the most simple way to do this question.
02:10Because there is an array palindrome or not.
02:12For that we have already written code.
02:14In fact, in the area, I can store all the data in the string.
02:17I can check whether my string is palindrome.
02:20I have already asked this question.
02:22I also know how to do this question.
02:24The most simple way to use any other data structure.
02:31If I use my string or my array list, then my link list will already have a palindrome.
02:37So in this case, I think big of n time complexity.
02:41And big of n space complexity.
02:44Why space complexity?
02:45Because I have used an extra data structure.
02:48But I am going to solve this question with linear time complexity.
02:52But constant space.
02:54We are not using any extra space.
02:55We are not using any other data.
02:56So we will solve it in that way.
02:58Then we will learn concepts.
03:00First of all, the step that I am going to perform.
03:03This is to find the middle.
03:06Or the middle node in your link list.
03:09Find it.
03:11The second step that I am going to perform.
03:13If I have found the middle node.
03:15If I have a link list in which there are nodes.
03:19Let's assume that this is an example of the link list.
03:21In which there are even cases.
03:23Even number of nodes.
03:25Or this is an example of my link list.
03:27In which there are odd number of nodes.
03:33So what can I say?
03:34What will this link list mean?
03:36This link list will come from me.
03:38This link list will come from me.
03:41This link list will come from me.
03:43This link list will come from me.
03:45and this link list will also be divided in two parts.
03:48Now what I have to do?
03:49I will reverse my second half
03:53I will reverse my second half
03:55Before I had written the code of link list
03:58Now I am going to reverse the second half
04:01and as I have reversed the second half
04:04then I will have a third step
04:06check if first half
04:10or left half
04:12that is equal to my second half
04:17which is my right half
04:20So in three steps I am going to do my work
04:23First step is to find out the middle node
04:25If you have found out the middle node
04:26then you know where to do the link list
04:29Second step is to reverse the second half
04:32Third step is to check if the first half is equal to my second half
04:38Now let's see this in an example
04:40First I will take my even case
04:44Even case it will say that my link list size is even
04:48this is my true description
04:56If I dig into account for nothing
04:56there is nothing
04:58The other way I have multiplied
05:01The other way I have sacrificed
05:06This is my 2, this is my 1
05:08Here is my head
05:12First step is to find out the middle node
05:15Now, what is the middle node is going to be for this link list?
05:18Middle node is going to be for this link list
05:21As I have found out the middle node, I know that I have to reverse reverse the middle node
05:28So, the first step I have to perform is to find out the middle
05:32Now, how will I do this step for finding out the middle?
05:34How will I do this step?
05:36The first step is to calculate the size from the beginning
05:41From the beginning, I will calculate the size of the middle
05:44Then I will calculate the middle as my size divided by 2
05:47But this also exists another easy way
05:50This is another easy way, which I call slow-fast technique
05:56What is the slow-fast technique?
05:58I can take two pointers
05:59I can take it like two pointers
06:03One is my slow pointer, which I will initialize with the head
06:07One is my fast pointer, which I will initialize with the head
06:31And this is my fast pointer, which I call hair
06:34Turtle is also my hair
06:34Turtle is also my hair
06:36Hair is also my hair
06:37So, my hair is also my hair
06:39So, my hair is also my hair
06:45And my hair is also my hair
06:50So, if I have some nodes
06:54So, I can take two pointers
06:56One is my slow pointer
06:58One is my fast pointer
06:59And if I want to find out the middle of the linked list
07:02I want to find out the middle of the linked list
07:04I want to find out the middle of the linked list
07:07I have a case in this linked list
07:19In which I have a case in 4 nodes
07:22Plugin, I move faster
07:22There will run the slow tweak
07:23goo in theseaja
07:25Coffee here
07:27Then I can take short来
07:28That's the last step
07:28What will the last step
07:31So, the first step
07:32Then I can take short、 parlé in here
07:33and my fast
07:35To be changed
07:36This wayji
07:44doesn't turn The
07:51null包括
07:52Until my fast is null to equal, as fast is null to equal, if I observe slow, where is slow?
07:59My slow is middle value. This is my middle value.
08:03I mean, if I put slow to 1, fast to 2.
08:08As fast is null in even notes case, where is slow?
08:12In that case, slow will be mid value.
08:15Automatically slow is increasing from 1.
08:17What did fast do to cover size? So, what will slow cover?
08:21Because slow is half.
08:23Fast is 2, slow is 1.
08:25That's why slow has half size.
08:28That is why, size by 2 has been covered by slow.
08:33So, what can I say? Slow is my mid.
08:35Because mid is equal to size by 2.
08:37I use this technique. This is even case.
08:40If I take odd example,
08:42I also take odd example.
08:44I mean, I see my linked list like this.
08:47In which there are 5 nodes.
08:483, 4, 5 and this is finally my null.
08:52If this is my...
08:54One condition is already coming.
08:56What is my first condition?
08:58This is my first condition.
08:59Until my fast is not equal to null.
09:02Until I have to run.
09:03This is my even case condition.
09:05If this is my slow and this is my fast.
09:08So, in the first step, slow is 1.
09:12Fast is here.
09:142.
09:14What is slow?
09:151.
09:16Fast is here.
09:18What will happen next?
09:19What will happen next?
09:19In the next step, slow is here.
09:21Fast is here.
09:25My fast is here.
09:25So, this has been here.
09:29Fast is here.
09:31But, what can I say?
09:32Fast is not going further.
09:33Fast is 2.
09:35Fast is 2.
09:351.
09:36I can hit the wrong button.
09:37The null will come.
09:38But, what is it?
09:39What is it?
09:39Nothing is there.
09:41Fast is not going further.
09:43So, where will it be?
09:45Fast is in odd case.
09:47Where will it be?
09:50Where will it be?
09:51Next will be null.
09:53We are all logically.
09:54We will write code.
09:56I will write code.
09:58I am explaining the middle.
09:59I am explaining the middle.
09:59In even case, I had understood.
10:01When will it be null?
10:02When will it be null?
10:03When will it be null?
10:05Next will be null.
10:06As we observe that fast is null.
10:09What is it?
10:11I have seen that slow is automatically in my mid.
10:13This is my linked list path size.
10:16What will it be?
10:17Mid is this node.
10:18And slow is automatically reached here.
10:21So, I have a condition that I can remove mid.
10:24Either fast is not null or fast is not null.
10:29Until this condition is true.
10:32Until I have to add slow and fast.
10:33Until I have to add slow and fast.
10:34As this condition is true,
10:36What will it be?
10:38That will be my middle node.
10:41That will be my linked list node.
10:42This is my slow and fast technique.
10:43In fact, once we make a function.
10:46In which we find a middle node.
10:48I am going to make a middle node.
10:50I am going to make a function.
10:52Public node.
10:53The node will be return type.
10:55I will give it the name.
10:56Find middle.
10:59Or find middle.
11:00In this case, I will always have a head as a parameter.
11:03The return type is node.
11:05What will I do?
11:06I will take a slow pointer.
11:08Slow will be initialized with the head.
11:10And a fast pointer.
11:11Fast will be initialized with the head.
11:13Now I have to add slow and fast.
11:16Now I have to run a loop.
11:17How do I run a loop?
11:18I have to run a loop until I run a loop.
11:19Until my fast is not equal to null.
11:23And my fast is not equal to null.
11:28Not equal to null.
11:30As if there is no condition is true,
11:33I will stop there.
11:35What will I do?
11:36I will get my middle.
11:39What will I do?
11:40Slow.next.
11:43Slow will move from 1 to 1.
11:45What will I do?
11:49Fast.next.next
11:53This will be plus 2.
11:55This will go from 1 to 2.
11:58This will go from 1 to 2.
11:59This will go from 1 to 1.
12:00This will go from 1 to 2.
12:01What will I do?
12:02While loop is complete.
12:03As this loop is complete,
12:05What will I do?
12:06My slow is my middle.
12:09I can say this.
12:10I will return directly from this.
12:12Slow.
12:14Slow is my mid-note.
12:17This is my whole method.
12:19What will I find out?
12:20To find out for any link list.
12:23Who have I used here?
12:25I have used my slow fast approach.
12:29Now I have completed step 1.
12:31What was the step 1?
12:32Step 1 was to find out your middle.
12:34If my link list is even size,
12:37It will also find out.
12:38If my link list is even size,
12:38It will also find out.
12:38If my link list is even size,
12:39It will also find out.
12:40That is the way I have learned.
12:41Now I will continue on my step 2.
12:44What is the step 2?
12:46What is the step 2?
12:46Step 2 is to reverse reverse the second half.
12:48If I have an example of this link list,
12:49I will reverse reverse the second half.
12:52It means that this node will point it.
12:56This node will point a null value.
13:01Because I have to reverse reverse the second half.
13:03I have to reverse this part.
13:05I have to reverse this part.
13:10So, this will point the null to the point.
13:13And this null will be removed.
13:16So, what happened? My second half is reversed.
13:18Second half is reversed. How will my linked list look?
13:22This is my one and this is my head.
13:24This is pointing to the two.
13:27This is pointing to the two.
13:30But this is pointing to the two.
13:34And one node is pointing to the one.
13:36This one is pointing to the one.
13:40My linked list will come in this state after reverse.
13:43What steps will be reversed?
13:45The same steps will be reversed.
13:46Which I have calculated mid to mid.
13:49I have to reverse reverse all the steps.
13:50So, I have written all the steps in reverse and linked list.
13:53Which one?
13:53Three variables and four steps.
13:55Three variables and four steps.
13:57But this time I will start from mid.
13:59I will not start from head.
14:00I will start from mid.
14:02So, we will understand these steps.
14:04Now, I will move on the third step.
14:06In the third step, I will check if my left half is equal to my right half.
14:11So, I will take two variables.
14:13This is my left, which will be initialized with the head.
14:17And this is my right.
14:20Can I say that my second half linked list will become the head?
14:25The head will become the head.
14:26At this height, the head is this.
14:30That's right.
14:30Because we are higher than that.
14:32And higher than that.
14:34We are more higher than that.
14:34So, the head of the second half will become the head.
14:37Which I will start from the head of the second half, I will start from the left.
14:41Then my second half will start from the right to the right.
14:43Now I will compare left with right. Is left value equal to right? Yes.
14:49I mean, these two nodes are satisfying. Then I will update them.
14:55I will update it and take it from here to this left.
15:03Now I will compare if left value is equal to right.
15:09Now I will update it and take it to next.
15:14This is here, left is my next. What is next? Right is null value.
15:22So right will come to null.
15:23Just like right is null, I will break it. I will not save anything to check.
15:28Obviously I will not save it. There were 4 nodes. I have checked the 4 nodes.
15:31I have compared it with this node and compared it with this node.
15:34And if you notice, this is the same thing that we did in string.
15:38If I had to check in string, A, B, B, A.
15:41What is the same? What did I say?
15:43First check for both of them. Then check for both of them.
15:46So in the middle, like I reached the middle,
15:49or until n by 2,
15:51I mean, if everything is the same here,
15:54I mean my string is a palindrome.
15:55And how did it be possible to traverse here?
15:58How did it be possible to traverse here?
15:59How did it be possible to traverse here?
16:01When I reversed the second half.
16:03So the second half to reverse is one of the most important steps.
16:07Because that's why we can traverse backwards.
16:10If we can't travel backwards,
16:11then we can't check the link list for the palindrome.
16:13We have to reverse backwards.
16:16So in three steps, I have checked if my link list is a palindrome or not.
16:20This is an even case.
16:22When my size was even.
16:25I mean, size is equal to 4K.
16:27Now I can check the same thing for my odd case.
16:31What will I do in the odd case?
16:32I will make a 3 size link list.
16:341, 2, 1.
16:39This is the point.
16:40This is the point,
16:41and this one point.
16:42Dieses the point.
16:44This is my head.
16:45What do I want to do is first,
16:47turn off mid.
16:48My mid will go through.
16:49What I will do the forest after?
16:51To go in the square with the middle part.answering
16:53I reversal the outp MP. What do
16:54the whole vibe. This is
16:55my head. This is
16:58my head. What does
16:58remove mid into mid. Once I
16:58am tiers, I procedures
16:59the double sized null value.ά York
17:07worker number-
17:09Now I have to do left and right thing. This is my first node, this is my second node, this
17:16is my third node.
17:17Now how do connections are here? This is pointing at the front. This is pointing at the next node.
17:25So I will start. This will be my left and this will be my right.
17:30First I will check if the data is equal to right. Yes, both are the same.
17:34Then I will increase this value. This will become my left and this will become my right.
17:44I will check again. If my left data is equal to my right data?
17:48Both data are the same. This will be true. Then I will increase this value.
17:53Then I will increase this value and increase this value.
17:57What will next be? This will be null equal.
17:59Now I will increase this value in this loop.
18:03I will increase this value in this loop.
18:04I will increase this value in my last link list and compare it with my second half.
18:09Now I am going to write the code for these three parts.
18:10Like the three steps. I will choose the code for the third step.
18:11To write code in the box and I am going to write 3 steps.
18:11I will write code for the total amount.