Palindrome Linked List - Leetcode 234 - Python

0:00 - Array solution
3:43 - Optimal Solution

Leetcode 234
#Coding #leetcode #neetcode

[ax]

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!

[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 <- 1 (3 points to null)
The left pointer is made to point to the the original head
The right pointer is made to point to the last node

So in the evaluating if it's a palindrome, they both share a final node
1 -> 2 -> 3 -> null
1 -> 2 -> 3 -> null

In a real world situation I'd be afraid to do this method because it corrupts the datastructure passed into it. You'd have to reverse the second half of the nodes again and make the tail of the first half point to the head of second half to restore it. I'd probably do the array solution irl, but I'm not aware of when in the hell you'd ever have to do something like this.

Ok case with even number of nodes is weird too.

1 -> 2 -> 2 -> 1
turns into
1->2-> 2 <- 1
where the right side 2 points to null
so evaluation takes goes through
1 -> 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.

[theendurance]

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

[yokohibarashi]

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.

[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.

[morty]

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

[mostinho]

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

[LOVEYOULOVEHERTOTHEINFINITY]

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

[ax]

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

[harunguven]

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.

[lqsamherst]

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.

[utkarshraz]

very effective and easy to understand thanks bro

[longchikanouo]

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

[mohamedhamza]

Your explanation is pretty good and clear, keep going

[sudheerranjan]

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

[sakhawathossen]

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

[koga]

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?

[ztluo]

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

[nikhildinesan]

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