Linked List Playlist: kzread.info/dash/bejne/eWSTq4-TdpO5Y5s.html

@OriMoscovitz

Жыл бұрын

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

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

2 жыл бұрын

array method is not tricky

@farazahmed7

2 жыл бұрын

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

@embarrassed_dodo

10 ай бұрын

@@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

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

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

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

10 ай бұрын

Great explanation thanks dude

@Iam_number_one

6 ай бұрын

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

@user-bu9ht7yq7s

4 ай бұрын

thanks, this is important

@fabiolean

3 ай бұрын

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

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

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.

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

Your explanation is pretty good and clear, keep going

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

FANTASTIC. Thank you!

amazing video man! Thank you!

Great clean simple explanation

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

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

@NeetCode

3 жыл бұрын

Thanks, I will!

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

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

Nice explanation 👍

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

@bhavyaseth4254

2 жыл бұрын

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

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

2 жыл бұрын

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.

awesome explanation

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

The optimal solution is so smart

Do we need to restore the list after checking palindrome?

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

thank you neet code

Awesome!

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

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.

Imma just use that array solution in an interview

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

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.

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

3 жыл бұрын

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

@visheshsharma5768

2 жыл бұрын

@@koga477 Help me understand it too :/

@koga477

2 жыл бұрын

@@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)

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

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

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

2 жыл бұрын

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

@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

neet explanation as always

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

Could you do this with a stack?

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

11 ай бұрын

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.

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

@joelbisponegrao9932

2 жыл бұрын

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

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.

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

@ramishakabir5816

2 жыл бұрын

just watched this: kzread.info/dash/bejne/eWSTq4-TdpO5Y5s.html and it makes a lot more sense. Saving it here if anyone else has a similar problem.

what about the even and odd thingy :/

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

@skms31

2 жыл бұрын

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

2 жыл бұрын

@@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

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

U a God

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

@BharathKalyanBhamidipati

2 жыл бұрын

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

2 жыл бұрын

@@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

10:46 got me😂😂

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]

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

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

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.

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

@sijiexiang8677

2 жыл бұрын

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

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

@symbol767

2 жыл бұрын

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 : kzread.info/dash/bejne/eWSTq4-TdpO5Y5s.html

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