Palindrome Linked List - Leetcode 234 - Python

[@NeetCode]

Linked List Playlist: kzbin.info/www/bejne/fWHCemCQe5WGaZo

[@OriMoscovitz]

You do have a tiny mistake there, using tmp on line 20 and then calling it temp in line 23

[@hehhehdummy]

Case with odd number of nodes is interesting Pointers before reversing: 1 -> 2 -> 3 -> 2 -> 1 -> null Pointers after reversing: 1 ->2 -> 3 2 -> 2 -> 1 turns into 1->2-> 2 2 -> 2 -> null 1 -> 2 -> null so logic short circuits once right side gets to null. A better visual of the 4 element case is seen at 9:03, but he doesn't really touch on this issue.

[@affafa100]

Thanks

[@embarrassed_dodo]

Great explanation thanks dude

[@Iam_number_one]

I think we do this method because our purpose is to return a boolean value , so we do not care that much about out data structure ; but I totally agree with you that i a real world , this could be an issue

[@呂政祺]

thanks, this is important

[@fabiolean]

Thank you. As good of an explanation as "sorta reversed it?" was 🤔. This helps a ton.

[@ax5344]

Gosh, this one is in the Easy category but it's so tricky with all those pointers. Glad to find you have a video on it!

[@kartikhegde533]

array method is not tricky

[@farazahmed7]

@@kartikhegde533 interviewer will not accept the array method. Its too trivial

[@embarrassed_dodo]

@@farazahmed7 I thought the same even though I saw the question and got it but didn't try to do in my own cause I knew it is a waste of time

[@yokohibarashi1386]

Great video. You are able to clearly explain complicated algorithms. You’re a great help. Thank you.

[@AverageHumanoid]

In case of the O(n) memory, instead of converting the whole LL into an array, I just pushed the slow ptr values into a stack and once fast ptr reaches the end, start popping out of stack to compare the stack with second half for palindrome check. This is far easier with one pass and half the extra array size as well.

[@theendurance]

Thanks man. There's a million of these Leetcode solution videos but yours are the clearest and most concise.

[@morty6975]

Actually, before solving this you should solve LeetCode 206 and 876 and you'll get what you need to solve this.

[@hamoodhabibi7026]

hamood thanks

[@charan_75]

this comment should be pinned

[@vivek2319]

Thanks

[@mostinho7]

Done thanks Solutions: 1. Put the items in an array then use left right pointers at each end, moving them towards each other to check for palindromes, this is O(n) space as it needs extra array 2. For o(1) space, keep it as linkedlist and again use two pointers, but first you have to reverse the second half of the linkedlist to be able to traverse it from the end to the middle. How do you get a pointer to the midpoint of the linkedlist? Efficient way: use fast and slow pointers, when the fast pointer reaches the end the slow pointer will be at midpoint. You can apply reverse linkedlist algorithm with the head being the midpoint of the linkedlist

[@aynuayex]

👏the second solution is out of this world really. it combine multiple leet code question solutions in to one find middle, reverse linked list and finally the challenge it self isPalindrome.

[@ax5344]

why odd and even length does not make a difference on the code identifying the mid point?

[@bhavyaseth4254]

It will automatically take the value which is at the left, If its odd and mid is 5.5 then ut will take 5 as the mid val

[@tomonkysinatree]

It doesn't make a difference because he uses the condition while right: when checking the palindrome. If even number of nodes -> while loop stops after length/2 iterations. If odd number of nodes -> while loop stops on the shared middle node

[@strong1134]

Than you my guy, wherever you are on this planet, you are making life easier for us

[@harunguven8581]

There is slight difference between this question and reorder list question. In both of them we find middle, reverse second half, but in reorder list question we slice both lists, in this question we don't need that. If anyone asks why both left and right list has common node but it doesn't throw error, because we go until right is null. This is not the same case as Reorder List problem, in that problem we have to slice list, we must go until both of lists, therefore we shouldn't have any common node.

[@sudheerranjan3374]

at 8:22, you mentioned that after reversing the second half the linked list would be 1->2->2None. But as we have set the next of middle element to None, shouldn't that be 1->2 and None

[@BharathKalyanBhamidipati]

while reversing, you use two pointers - prev and slow. By the end of the loop, slow would be None, and prev would be 1. 1(here) is the head of your reversed list. So, revhead = prev

[@nayanagopinath669]

@@BharathKalyanBhamidipati Could you please elaborate

[@hamoodhabibi7026]

You are correct so it's more like None ^ 1 -> 2 -> 2 None so the top None is from prev the first time it's initialized and the right None is the stop condition for "while slow" Thus we don't change the link/direction for that one since loop ends :) But top None is still important wwhen we traverse it in the other direction for #check palindrome and the code "while right" and the reason why we do right instead of left is bcz: left: 1-> 2 -> 2 -> None right: 1-> 2-> None

[@lqsamherst9546]

It's a really good video and I think here is a little detail that should be noticed: Once we finished reversing the right link list, actually the left link list is 1 length longer than the right one. For example, for [1,2,2,1], left one is [1,2,2,None] and the right one is [1,2]. The reason for this in my opinion is that the previous one of the middle still pointing the middle as the next node and does not change via the second loop(the border for the second loop is the middle, not the middle's previous one) so it causes the difference of length. Maybe I'm wrong, please comment if you want to correct me.

[@dkdlife6210]

In the case [1,2,2,1] we have: left = [1,2,2,None], right = [1,2,None]. Another case is [1,2,3,2,1] =>> left = [1,2,3,None], right = [1,2,3,None] In both cases above we just use (while right:) to check it is Palindrome or not.

[@longchikanouo4905]

Hi , here are two excerpts from two of your solutions for finding the middle element. two different implementations, please can you explain the difference: #1.Reorder linkedList #find middle slow, fast = head, head.next while fast and fast.next slow=slow.next fast = fast.next #2. isPalidrome linkedList #find middle(slow) slow, fast = head, head while fast and fast.next: fast = fast.next.next slow = slow.next

[@untrall6667]

好兄弟 我也发现了这个问题

[@hamoodhabibi7026]

Did u mean fast = fast.next.next for "#find middle"? If so, the difference is when the length of our linked list is even and there are two middle nodes: In #1 slow will end up being the 1st middle node In #2 slow will end up being the 2nd middle node

[@mohamedhamza6276]

Your explanation is pretty good and clear, keep going

[@nikhildinesan5259]

Great explanations...ur videos really helps to understand the concept and solve it....keep it coming...

[@NeetCode]

Thanks, I will!

[@utkarshraz9900]

very effective and easy to understand thanks bro

[@sakhawathossen2104]

Your voice is now more cheerful in present time (in the future from this video I guess) .

[@Nikhil-Tomar]

IF I traverse the LL to the very down and have the first_head carried to the very bottom, And then check if the first_head == current_head. If it is equal, we move the first_head = first_head.next, and move up the call stack because recursion is used here.

[@expansivegymnast1020]

FANTASTIC. Thank you!

[@grishmapatel7688]

Good explanation. However How reversing half of the list manages results for odd length?

[@joelbisponegrao9932]

you just need to add after the block find middle: if fast: slow = slow.next

[@blackswan2020]

@@joelbisponegrao9932 not clear

[@hamoodhabibi7026]

what do you mean? the code "while fast and fast.next:" takes care of that for us and ensures we get slow as mid point for either even or odd length... and the rest for reversing should can be the same code

[@koga477]

I'm incredibly confused by the reversal part. Everything else is clicking. Does anyone know where I can find an in-depth visual explanation for that part with the python solution?

[@koga477]

Nevermind, understanding the general practice of how a linked list is reversed rly helped

[@visheshsharma5768]

@@koga477 Help me understand it too :/

[@koga477]

@@visheshsharma5768 watch a video on how to reverse a linked list, the explanation is the exact same

[@Ryan-xb1ry]

@@visheshsharma5768 I also got confused but now I understand. Assuming the second half is 2 >> 1 >> None, it will look like this when it does the first iteration, None(prev)

[@huaxingwang2557]

why do we have to find the middle of the linked list, can we just reverse the whole linked list and check if they are the same?

[@NeetCode]

Yes, that is also a valid solution! The only down side is, I think in that case you will need O(n) memory to store the original order of the linked list.

[@programmer8064]

The optimal solution is so smart

[@orangethemeow]

Do we need to worry about whether the number of nodes is even or odd?

[@skms31]

Yea , even I have that question , if we have a list = 1>2>3>2>1 , the listA is 1>2 and then 1>2>3 after reversing. So do we ignore the number 3 ? Do we only compare 1 and 2 , what happens to 3?

[@orangethemeow]

@@skms31 I think I got the point. For 1>2>3>2>1, it will turn into 1>2>33>3>2>1 will be reversed as 1>2>3>3

[@ztluo8824]

The "prev" just does not make sense how can it store a reversed linked list?

[@kv366]

This even works with just stopping the final while loop the moment right == mid_point.

[@BobbyMarshallYT]

I like how the 1st solution was comparatively more space efficient.

[@kenjimiwa3739]

Great clean simple explanation

[@blueecloud24]

I'm curious how to make sure the slow pointer stops at the midpoint by shifting the left pointer twice and shifting the slow point once?

[@bossmusa9075]

simple logic ig. If rabbit goes 2 footsteps and turtule 1, then when it will be 6 footsteps for rabbit it will be middle 2 footsteps for turtule.

[@Morimove]

i thought reversing the LL can be a solution but also thought that changing the whole data structure is not good!

[@schan263]

Do we need to return the partially reversed linked list back to original state?

[@nemesis_rc]

Nice explanation 👍

[@charan_75]

Do we need to restore the list after checking palindrome?

[@georgeli6820]

amazing video man! Thank you!

[@codingninja01_]

10:46 got me😂😂

[@rishabhbajpai6234]

your reversing the linked list and array solution both are taking the same space ? why ?

[@lingyuhu4623]

Love all your videos! concise and clear~ How can I get access to all the Leetcode explanations by you?

[@ch33ze0g]

Imma just use that array solution in an interview

[@pythonicd1239]

After 7:40 it sorta just went over my head. Can anyone help?

[@charan_75]

watch and understand reversing a linked list before doing this.

[@charan_75]

solve LeetCode 206 and 876 and you'll get what you need to solve this.

[@therockriders2759]

This is the middle of a linked list + Reverse a linked list

[@tylerhurley5704]

Not sure if it is cheating or not, but when I solved this I just added a previous attribute converting the input singly linked list nto a doubly linked list. At that point it is just a simple two pointer problem

[@sneak0074]

explain please

[@swarupsarangi734]

awesome explanation

[@ramishakabir5816]

Can someone explain how the reverse linked list is created? I cannot seem to grasp it.

[@ramishakabir5816]

just watched this: kzbin.info/www/bejne/fWHCemCQe5WGaZo and it makes a lot more sense. Saving it here if anyone else has a similar problem.

[@caveman601]

Could you do this with a stack?

[@anmolbakshi7983]

thank you neet code

[@akashsinghbisht6448]

why didn't we reversed the complete list and compared head to head both the list ? will it be not possible ?

[@charan_75]

It will fail, the mismatch can be somewhere in middle. ex [1,1,2,1]

[@EverythingTechWithMustafa]

neet explanation as always

[@khuzaimaarham3795]

what about the even and odd thingy :/

[@chloecc7491]

I still don't get reverse the second half part, It's so ANNOYING!!!!

[@iscoto4914]

class Solution: def isPalindrome(self, head: Optional[ListNode]) -> bool: s = '' while head: s += str(head.val) head = head.next print(s[::-1]) if s == s[::-1]: return True else: return False

[@sneak0074]

o(n) space complexity

[@skms31]

at line 28 , while not use .. while left!=None

[@sijiexiang8677]

In the odd case, either left!=None or right!=None is fine. In the even case, we have left: 1->2->2->None we have right: 1->2->None Therefore in order to compare all nodes, we have to use right!=None

[@AustinWeeks]

if we want to support the channel, what? IF WE WANT TO SUPPORT THE CHANNEL WHAT?

[@sudharshanchakravarthy7199]

Awesome!

[@demiann4160]

Do you all agree this one should belong to the Easy category?

[@symbol767]

No because the optimal solution is difficult and annoying. Also because the interviewer may want you to also reverse the linked list back to its original format before returning, which makes it more tough

[@computerlearningbyargusaca5217]

• 🙏🙏First of all thanks for 👍👍uploading this video it was very helpful . 😍😍looking for more content 👌👌

[@edwardteach2]

U a God

[@rmiliming]

Thank you for the good video. but I feel this is better watched together with one of your other video on reversing a linkedlist : kzbin.info/www/bejne/fWHCemCQe5WGaZo