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.
👏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.
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
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
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.
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.
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.
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
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
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?
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.
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
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
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)
just watched this: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-G0_I-ZF0S38.html and it makes a lot more sense. Saving it here if anyone else has a similar problem.
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
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 : ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-G0_I-ZF0S38.html
