Data Structures in Python: Singly Linked Lists -- Is Palindrome

In this video, we investigate how to determine if a singly linked list is a palindrome, that is if the data held at each of the nodes in the linked list can be read forward or backward to generate the same content. We code up the solution to both of these approaches in Python.

The software written in this video is available at:

Do you like the development environment I'm using in this video? It's a customized version of vim that's enhanced for Python development. If you want to see how I set up my vim, I have a series on this here:

If you've found this video helpful and want to stay up-to-date with the latest videos posted on this channel, please subscribe:

[nataliatenoriomaia]

I hit "like" even before start watching your videos because I know it's guaranteed to be good.

[kousikbhandary]

Your approach is the simplest and superb. I'm prom non-programming background and by your videos I can easily understand data structures. Awesome.

[deepanshudashora]

I loved this tutorial, so good and far better than those approaches of other tutorials yo are killing it . Thanks for teaching us.

[sprret]

Thank you so much for these fantastic tutorials. You are a gentleman and a scholar!

[amritmadhav]

Sir,
Your approach and explanation is too good, simply great..
Thanks

[ShivamSingh-kngz]

I wish you'll read my comment until the end.😊😊

I tried this in a different manner, but I got stuck in later. My concept was to store the reverse of the LinkedList in a pointer variable using the original LinkedList and finding the length of the LinkedList too, then moving on with the for loop like around half of the length of LinkedList, in order to compare each the original and reverse linked list pointer data with each other, by increasing the original and decreasing the reversed pointers of both nodes by one in every iteration. But the thing that made this not to work was, after reversing the linked list, the pointer features in the programming language appear to change my original list pointer variable too.
I was stuck up until now. But, all thanks to you, All my doubts are cleared. Your tutorials are meant to get more values, just because the content in it is too valuable.
Hope I could connect with you at some media,
Regards Shivam, 😎
Love from India😍

[davidrowlands]

Yet another excellent video. Thank you.

[amraly]

A promising channel!. keep up the great work ;)

[idan]

last solution: I think its to access only the list (seen) instead of using the linked list for the comparison stage. (list is probably implemented with an array which means it would be faster to iterate/access its consecutive (in memory) elements

[RaboundTeam]

Is there a practical difference between iterating over the linked list with "while p:" and "while p.next != None"? I noticed some other books use the latter but to me they are functionally the same, is that true?

[sudhanshulodhi]

sir i have a problem for cloning the list i have 4 node in my linked list for making clone linked list is i have to make another 4 node for storing the value original linked list pls tell me about that

[davidrowlands]

Which one has the best time complexity?

[VikramKumar-tkwg]

sir which competitive site is good for practicing basic data structure problem which proves beneficial for us in questions asked in job interviews also..

[bharatapar]

what is the use of q=prev[i-1] in method 3 ? q value is not used after that line.

[sakshikamboj]

Is it important to know all the methods or should we go for the one which is more clear to us ?

[shivrajnag]

Method 3 is not worthy because we use Linear Space. I thought using two pointers we can reduce the space complexity but it has no impact on Space.

[EverPaiNn]

Do we really need "count <= i//2 + 1" ? I think with "count <= i//2" it works too.
Thanks for the videos, they help me a lot.

[codeset]

in palindrome checking if nodes data are integers then string method will fail

[LearnCodeDesign]

def is_palindrom(self):
if self.head is None:
return True
slow = self.head
fast = self.head
slow_prv = None
while slow and fast and fast.next:
slow_prv = slow
slow = slow.next
fast = fast.next.next
if fast:
# Linked List has Odd number of nodes
# and the last node pointed by fast pointer
# slow is the middle node
# Reverse the first half nd check with next half
p = slow.next
else:
p = slow
slow_prv.next = None
self.reverse_iterative()
q = self.head
while q and p:
if q.data != p.data:
return False
p = p.next
q = q.next
return True


This uses O(1) Memory