- 15 hours ago
Transcript
00:00I will write a function for the code. I have already find mid. This is my helper function. I will
00:06use this function.
00:07Now, I will write a function for the palindrome of public boolean. It will return true.
00:14If it is palindrome or not, it will return false.
00:17I will give it the name of check palindrome.
00:22I don't have to do anything in check palindrome. I have already my link list.
00:26What is the first step? Step 1 is to find mid.
00:33What will be step 2? Step 2 is to reverse second half.
00:38What will be step 3? Step 3 is to check left half and right half for palindrome.
00:47Before I write these three steps, I will write my base case or corner case.
00:51If my head is equal to null.
00:55Meaning my link list is empty.
00:57Or my head is next equal to null.
01:02Head is next equal to null.
01:04It means that the link list is one single element.
01:06If the link list is empty or the link list is one node.
01:10What happens in that case?
01:11The link list is automatically palindrome.
01:12So I will return true.
01:16Now what will I do for step 1?
01:18For step 1, my middle node will be equal to find mid node function.
01:26I will call this slow and fast approach.
01:28I will return my middle node.
01:30So I will call here.
01:33Find mid function.
01:35I will pass my head.
01:37Then I will have my middle node.
01:39Now I will reverse my second half.
01:41I will reverse the middle node.
01:42I will reverse the middle node.
01:44I will reverse the middle node.
01:45I will reverse the middle node.
01:46I will reverse my reverse steps.
01:48Now I will define three variables here.
01:52One is my previous.
01:54What will be null to equal?
01:56One will be my current.
01:58What will be current?
01:59It will be mid node.
02:00One will be my next.
02:02Now I will run a loop until my current is not equal to null.
02:07Now I will notice that I am writing the same code.
02:10Ditto.
02:11I am writing the same code that I have written in the reverse function.
02:14In fact, the reverse function is here.
02:18I am writing the same code.
02:20In this code, there will be a single change.
02:23What will be a single change?
02:24The initialization will be different.
02:25I mean, I had head current here.
02:27Because I have to reverse the second half.
02:29If I have to reverse the second half,
02:29then my current will become the middle node.
02:32How did I reverse?
02:33First of all, find out next.
02:35Next is equal to current.
02:38Next is equal to current.
02:38Next is equal to current.
02:40Next is equal to current.
02:42Previous is equal to current.
02:44And my current is equal to next.
02:47In this way, I have to reverse my linked list.
02:49I have to reverse reverse.
02:52Now, in last, I will take another parameter or another variable.
02:57With the name of right.
02:58What will I write?
02:59This is my right.
03:00Or I can call it right of head.
03:04Right half of head.
03:07What will it become?
03:09This will become my previous.
03:11Like my current is equal to current.
03:13Like my current is equal to previous.
03:13I mean, my previous node was my last node.
03:17Now, my head will become my second half.
03:19So, my previous will become my right half of head.
03:22What is my left half of head?
03:24That is my head value.
03:26This will become a statement terminator.
03:28So, my right half of head will become my previous.
03:31And my left half of head will become my head.
03:34Now, I have to perform step 3.
03:36I have to perform step 3.
03:37I have to check if my left half of my right half is equal.
03:40Now, I will run a loop.
03:41This loop will go until the end.
03:42Until my right is equal to null.
03:44I will not reach the second half.
03:46I will not reach the null.
03:48What will I do until I have to check?
03:50I will check if my left half of the data is not equal to right.
03:55Where it is not equal to.
03:56Where it is not equal to.
03:57Where the left half of the data is not matched with the right half of the data.
04:00I have to know that there is no palindrome.
04:02And I can do false returns.
04:05So, I will return false here.
04:07And if this is true,
04:09I will check both of them.
04:11Then I will check the next notes.
04:12So, I will make the left next.
04:17And I will make the right.
04:18I will make the right next.
04:20So, this is left next.
04:22This is right next.
04:23And I have checked.
04:25When did I check?
04:26Until my right is null.
04:28And what will I return?
04:30I will return true.
04:32If I have not done false returns,
04:34I will not get mismatching values.
04:36If I have not gotten mismatching values,
04:38I will return true.
04:40So, my link list is a palindrome.
04:43I will summarize it a little bit.
04:45I will summarize it.
04:47I have checked palindrome in three steps.
04:49The first step was to find middle node.
04:51I have used my slow-fast approach.
04:54As fast pointer will reach my last point,
04:57my slow pointer will reach half of the link list.
05:00So, I got middle node.
05:01Step two was to reverse second half.
05:03So, if I take current to middle node,
05:06I can write the same operations.
05:08I can reverse my second half.
05:10Then, what did I do?
05:11I have removed the right half of the head,
05:12which was my previous.
05:13And I have removed the left half of the head,
05:15which was my head.
05:16Then, I checked.
05:17Until my right is equal to null.
05:19If my left data is equal to my right data,
05:22then I will return false.
05:24If not, I will update them again.
05:27And I will return true.
05:29So, here I have completed my check palindrome
05:32and here I have completed my find mid function.
05:36What I am going to do?
05:37In the main function,
05:38I have already made a palindrome in a link list.
05:41And this is how I see the link list.
05:43One is pointing to two.
05:44Two is pointing to three.
05:45Two is pointing to two.
05:47One is pointing to one.
05:48I will also print it.
05:50And after that,
05:51I will call the check link list.check palindrome.
05:57Let's save and run.
06:03What is my output?
06:05The output is true.
06:07If I remove this node,
06:11and now my link list will become one to two.
06:14If I run this,
06:18I will return true.
06:18So, this time I have also output true.
06:20We have missed something.
06:23This is the check palindrome.
06:25We have written the case.
06:26Here, I have written not equal to null.
06:28I have written equal to equal to null.
06:30Because if not equal to null is true,
06:32then I will return true in every condition.
06:35So, here,
06:35head.next
06:36If it is null,
06:37I will return true.
06:39Let's do this.
06:40Save and run one time.
06:41Then the output will come to me.
06:43False to equal.
06:44In fact,
06:45I can make another link list.
06:46If I do this one to one,
06:48I will return true.
06:49In this case,
06:50I will return true.
06:53So, we will check whether my link list is a palindrome
06:56or not.
06:57I will summarize it a little more.
06:59I have written two functions.
07:01The main function is my check palindrome.
07:04What is the check palindrome?
07:04What is the check palindrome?
07:05First, we can see this case.
07:06If the head is null,
07:07and the next head is null,
07:09then I will always have a link list.
07:11After that,
07:12I will find out the middle.
07:13How do I find out the middle?
07:15From slow-fast approach.
07:16In which,
07:17I will add slow pointer to plus one.
07:19From fast pointer to plus two.
07:20As the fast pointer will reach last,
07:23where will my slow pointer reach?
07:25Middle.
07:26So, I have returned here.
07:28Middle node value.
07:29Then my second step is reverse.
07:31I have taken the second half.
07:32I have taken the three variables.
07:33I have taken the current and previous.
07:34I have taken the next.
07:35I have performed four steps.
07:37I have initialized next.
07:38After that,
07:40I changed the current and next value.
07:42Then I have updated previous and current.
07:43Last,
07:44what I have done?
07:45I have taken the right half.
07:46I have taken the previous head.
07:48And the left half.
07:49I have taken the head of the linked list.
07:51Then I have checked that
07:52until my right is null.
07:54It is not equal.
07:54It means,
07:54it is traversed from the back.
07:56The second half is not finished.
08:00Until I have left half.
08:01I am comparing the right half.
08:03If it is not equal to,
08:05I have returned false.
08:06In other cases,
08:07I have updated left to next.
08:09And right to next.
08:11And last,
08:12I have returned true.
08:13So,
08:14in this way,
08:15we can check any questions.
08:16In the linked list,
08:18if a linked list is a palindrome or not.
08:20It is a palindrome.
08:20It is a palindrome.
08:20We can goyle.
08:20We can do it.
08:21And another one.
08:21We are on the left.