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.
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
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.
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
👏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.
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
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.
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
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
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.
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.
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?
@@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)
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
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
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
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
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.
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.
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?
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
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
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
Thank you for the good video. but I feel this is better watched together with one of your other video on reversing a linkedlist : ua-cam.com/video/G0_I-ZF0S38/v-deo.html
Linked List Playlist: ua-cam.com/video/G0_I-ZF0S38/v-deo.html
You do have a tiny mistake there, using tmp on line 20 and then calling it temp in line 23
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.
Thanks
Great explanation thanks dude
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
Thank you. As good of an explanation as "sorta reversed it?" was 🤔. This helps a ton.
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!
array method is not tricky
@@kartikhegde533 interviewer will not accept the array method. Its too trivial
@@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
Great video. You are able to clearly explain complicated algorithms. You’re a great help. Thank you.
Actually, before solving this you should solve LeetCode 206 and 876 and you'll get what you need to solve this.
hamood thanks
this comment should be pinned
Thanks
Thanks man. There's a million of these Leetcode solution videos but yours are the clearest and most concise.
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.
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
👏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.
why odd and even length does not make a difference on the code identifying the mid point?
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
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
Than you my guy, wherever you are on this planet, you are making life easier for us
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.
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
好兄弟 我也发现了这个问题
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
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.
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.
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?
Nevermind, understanding the general practice of how a linked list is reversed rly helped
@@koga477 Help me understand it too :/
@@visheshsharma5768 watch a video on how to reverse a linked list, the explanation is the exact same
@@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)
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
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
@@BharathKalyanBhamidipati Could you please elaborate
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
Good explanation. However How reversing half of the list manages results for odd length?
you just need to add after the block find middle:
if fast:
slow = slow.next
@@joelbisponegrao9932 not clear
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
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?
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.
Great explanations...ur videos really helps to understand the concept and solve it....keep it coming...
Thanks, I will!
The "prev" just does not make sense how can it store a reversed linked list?
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.
Your voice is now more cheerful in present time (in the future from this video I guess) .
Do we need to worry about whether the number of nodes is even or odd?
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?
@@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
Your explanation is pretty good and clear, keep going
I like how the 1st solution was comparatively more space efficient.
very effective and easy to understand thanks bro
This even works with just stopping the final while loop the moment right == mid_point.
FANTASTIC. Thank you!
Love all your videos! concise and clear~ How can I get access to all the Leetcode explanations by you?
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?
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.
i thought reversing the LL can be a solution but also thought that changing the whole data structure is not good!
The optimal solution is so smart
Great clean simple explanation
10:46 got me😂😂
Do we need to return the partially reversed linked list back to original state?
Do we need to restore the list after checking palindrome?
your reversing the linked list and array solution both are taking the same space ? why ?
Nice explanation 👍
amazing video man! Thank you!
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
explain please
Can someone explain how the reverse linked list is created? I cannot seem to grasp it.
just watched this: ua-cam.com/video/G0_I-ZF0S38/v-deo.html and it makes a lot more sense. Saving it here if anyone else has a similar problem.
After 7:40 it sorta just went over my head. Can anyone help?
watch and understand reversing a linked list before doing this.
solve LeetCode 206 and 876 and you'll get what you need to solve this.
Imma just use that array solution in an interview
awesome explanation
This is the middle of a linked list + Reverse a linked list
why didn't we reversed the complete list and compared head to head both the list ? will it be not possible ?
It will fail, the mismatch can be somewhere in middle. ex [1,1,2,1]
• 🙏🙏First of all thanks for 👍👍uploading this video it was very helpful . 😍😍looking for more content 👌👌
Could you do this with a stack?
thank you neet code
I still don't get reverse the second half part, It's so ANNOYING!!!!
what about the even and odd thingy :/
neet explanation as always
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
o(n) space complexity
at line 28 , while not use .. while left!=None
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
Awesome!
if we want to support the channel, what?
IF WE WANT TO SUPPORT THE CHANNEL WHAT?
Do you all agree this one should belong to the Easy category?
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
U a God
Thank you for the good video. but I feel this is better watched together with one of your other video on reversing a linkedlist : ua-cam.com/video/G0_I-ZF0S38/v-deo.html