Palindrome Linked List & Find the middle of a Given Linked List | DSA-One Course #38
Palindrome Linked List & Find the middle of a Given Linked List | DSA-One Course #38
Hey guys, In this video, We’re going to solve an interesting problem on Linked List called : Check if a Linked List is Palindrome or not. We’ll also learn how to find the middle of a Given Linked List.
Practice problems here: https://www.interviewbit.com/courses/…
🥳 Join our Telegram Community:
Telegram channel: https://telegram.me/realanujbhaiya
Telegram group: https://telegram.me/dsa_one
🚀 Follow me on:
Instagram: https://www.instagram.com/Anuj.Kumar…
Linkedin: https://www.linkedin.com/in/sharma-ku…
Twitter: https://twitter.com/realanujbhaiya
💸 Use coupon code ANUJBHAIYA on GeeksforGeeks to avail discounts on courses!
📚 Complete DSA Playlist: • DSA-One Course - The Complete Data St…
Complete Android Development Playlist: • Android Development Tutorial for Begi…
Hashtags:
#anujbhaiya #dsaone
Ignore these tags:
palindrome linked list
linked list
palindrome linked list leetcode
palindrome
234. palindrome linked list
palindrome linked list java
leetcode palindrome linked list
linked list palindrome
palindrome linked list solution
234 palindrome linked list
palindrome linked list python
linked lists
palindrome linked list 234
palindrome linked list c++
palindromic linked list
if linked list is palindrome
palindrome linked list algorithm
reverse linked list
find the middle node of a linked list
linked list
middle element of linked list
middle of linked list
find middle element of linked list
middle node of linked list
middle of the linked list
find middle element of a linked list
find the middle of a given linked list in c
find the middle of a given linked list
find the middle of a singly linked list
find the middle element of a given linked list
find the middle element of a singly linked list
palindrome linked list
palindrome linked list leetcode
palindrome
linked list
leetcode palindrome linked list
linked list palindrome
palindrome linked list java
234. palindrome linked list
palindromic linked list
234 palindrome linked list
palindrome linked list python
palindrome linked list solution
leetcode 234 palindrome linked list
palindrome linked list c++
palindrome linked list 234
if linked list is palindrome
palindrome linked list algorithm
Content
0 -> Hey, what's up guys?
1.044 -> Welcome to the DSA-ONE Course
2.23 -> and today we're gonna solve one more question on Linked List
4.101 -> which is Palindrome Linked List
6.118 -> Basically, a linked list will be given to you
7.951 -> and you have to tell
9.184 -> the data points or data elements in that linked list are making palindrome or not
16.367 -> you may know what is Palindrome String?
18.033 -> Palindrome String is a string which when reversed is same as the original string
23.467 -> now similarly, here you have to tell whether this given linked list is palindrome linked list or not
29.567 -> so I have taken two examples
31.383 -> both of them are palindrome, you can check it
33.051 -> there is one more way to check palindrome
35.451 -> that you may check 'R' and 'R', 'A' and 'A'
42.251 -> then 'C' and 'C' , then 'E'
44.301 -> are they equal or not?
45.951 -> Similarly, 'A' and 'A' are equal
47.584 -> 'B' and 'B' are equal
49.018 -> or there is another way
50.418 -> that we reverse the first linked list
54.05 -> and we'll check reversed linked list and original list
57.318 -> if they are same
59.583 -> then it's a palindrome too
61.834 -> Suppose, we reverse the second linked list
64.451 -> and then check, the respective elements are same or not
75.418 -> so you can check in this way too
77.967 -> and tell, yes it's a palindrome linked list
80.784 -> but you're using a different space in this case
84.384 -> you're already having a linked list
86.418 -> you made a duplicate one
90.551 -> and you used a space called
93.151 -> Big of N space which is not allowed in it
97.801 -> You have to use constant space in it
100.767 -> and you also can't think to use this linked list in array
105.451 -> and then will keep checking front and back pointers in array
107.334 -> that's also not allowed
108.234 -> because you'd be using big of N space there too
110.884 -> So big of N space is out of picture
113.217 -> now you have to modify this linked list only
119.517 -> So that you keep checking the front and back elements
124.933 -> you don't have to put this in array
128.268 -> You have to modify this in a way that you can compare
131.701 -> the respective front and back elements
134.434 -> but here you can see you can't do this way
138.801 -> because every element is not having the pointer of the consecutive one
147.067 -> now you think how can you achieve this
151.617 -> After that I'll tell the whole logic behind this
154.418 -> You'd have seen
155.868 -> there is no way of coming to
157.95 -> second last element from last element
164.35 -> So we reverse this part
168.5 -> basically I keep half list same
173.683 -> and other half list reversed
182 -> Now these links will disappear
185.383 -> I will start
187.001 -> one pointer from end and one from start
190.768 -> And if they are same we'll continue
200.766 -> And when both are equal, we can come out
204.283 -> then we can say the linked list is palindrome
207.933 -> and if I see somewhere the elements are not equal
210.851 -> I can say it is not a palindrome
214.466 -> Now another question
216.816 -> how to reverse linked list
219.983 -> which I have already told
224.567 -> now let's see how to reverse only the half part
237.267 -> here the procedure is same too
241.783 -> You may know the reverse function
245.933 -> And it takes the head inside it
251.85 -> but you can pass any node inside it
254.118 -> It will reverse the linked list after that node
255.734 -> This function catches the node
257.317 -> and reverses the linked list after that node
267.7 -> if you pass head in this function
270.433 -> it will reverse the whole linked list and return last point
274.533 -> but if you pass middle node
280.484 -> it will start from middle and reverse the next part
286.917 -> so you will pass mid, not head
289.767 -> pass mid and it will reverse that part to give that pointer
295.418 -> now you see half part is correct and half reversed
300.834 -> now question is how to bring that mid pointer
309.189 -> This is a question in itself
313.314 -> So now let's try to solve this question
315.122 -> what is a middle pointer in a linked list
316.635 -> How to find out that
318.1 -> Ok
318.837 -> We use Fast Slow pointer approach for that
321.797 -> What do we do in that?
323.649 -> One pointer moves fast and other one slowly
326.925 -> As soon as fast pointer reach null, slow ones reaches the mid
330.917 -> You can take this example. Let's say a man is running at a speed of 10km/hr
335.446 -> and the other one is running at half of his speed which is 5 km/hr
338.866 -> Then, after 1 hour, The first person will be at 10km distance, while the second one will be at 5 km distance
351.779 -> Right
352.84 -> We are going to use this same approach in our solution
355.019 -> We will keep two pointers, one fast and one slow
356.691 -> Fast pointer will take 2 steps at a time, while the slow one will move with single steps
362.751 -> Fast Pointer will take 2 steps, slow one will take 1 step
367.071 -> Again Fast Pointer will take 2 steps, slow one will take 1 step
369.837 -> Again Fast Pointer will take 2 steps, slow one will take 1 step
376.28 -> When the fast pointer will reach the end of the linked list, at that time the slower one will be at the middle node
384.951 -> This is how we are going to find the middle pointer
390.233 -> We will pass this middle pointer in the reverse function
392.823 -> This reverse function will give us the pointer to the last node and then we can keep on comparing both of these end nodes
404.845 -> This is how we will check whether this linked list is a palindrome or not
406.725 -> This is going to be it's logic
408.493 -> Now try to write a code for this. I will also show the code, but first try it yourself
414.624 -> This is the code for this question
419.389 -> This function returns a boolean value. You pass a linkedlist to it and it will tell whether it is palindrome or not
424.249 -> If the head is NULL, then return true
430.916 -> Then first we will find the middle, as we discussed earlier
435.421 -> See, if we have a linked list like this, then we will try to find the middle element in it
442.063 -> I have made a function named 'Middle' for that
444.463 -> It takes head node as a parameter and then return the middle node in this linked list
449.447 -> We are using two pointers for that - Slow pointer and fast pointer
453.235 -> Slow pointer will move by 1 step while the fast pointer will move by 2 steps
459.257 -> These are the conditions for this while loop to run
464.848 -> Slow = slow->next, which means 1 step
468.187 -> Fast = Fast.next.next, which means 2 steps
471.242 -> and as long as you will do this
473.884 -> Let's suppose, you are here
476.09 -> Both slow and fast pointers are here
478.305 -> First we will check whether the Fast is NULL or not. No it is not in this case
483.642 -> So our slow pointer will move one step further
491.194 -> Fast will move to here
496.681 -> Now again we will check whether the Fast is NULL or not. No it is not in this case
504.175 -> So our slow pointer will move one step further
508.921 -> Fast will move to here
513.392 -> Then again, we will check whether the Fast is NULL or not. Yes it is NULL, then this loop will break here
522.05 -> So you can slow, our slow pointer is already at the middle position
524.879 -> So this function will return the middle pointer
531.331 -> Now to get the last node, we will call the reverse function
536.702 -> If you don't know, how this reverse function works, then you can watch the previous video of this playlist
541.211 -> There I have explained- how this reverse function works
545.214 -> so this will return pointer to the last node of the list
550.626 -> I have passed mid.next instead of mid. You will come to know, why I did so
558.331 -> I have passed pointer to B instead of C
563.123 -> So it will return the pointer to the last node, which is A
578.289 -> This head and that one is last
586.04 -> Now this half part of the list is reversed
589.115 -> Now simply, we will point Curr to head
592.917 -> We will move step by step
596.072 -> First we will check whether first is equal to last. If it's true, we will move both of these pointers forward
605.018 -> While last !=NULL
610.038 -> We will check whether last.data!=First.data
616.82 -> We will return false because it is not satisfying the condition of Palindrome
619.661 -> Otherwise, current=current.next
623.073 -> Now our current will come to here
627.801 -> and Last will move to B
633.196 -> Now again, we will check whether last !=Null
637.748 -> If last.data!=curr.data
641.468 -> No, both are equal, so again we will move these pointers by 1 step
654.725 -> So now, our last pointer is pointing to NULL, so our loop will break
660.629 -> and we will return true
661.583 -> So now, you must have understood why I passed mid.next instead of mid
665.813 -> This code will work for both Odd and even number of nodes
671.892 -> Let's suppose you have we have another node here 'X'
676.454 -> Then in that case, this would be your mid and we will reverse this part of the list
682.76 -> and our loop would have terminated here
687.126 -> But our code is working fine for ODD number of nodes too
693.949 -> You need not to check the middle element if the total number of elements are ODD
705.486 -> C is equal to itself so we need not to check it
713.636 -> So this is how ODD and EVEN works
716.991 -> I hope you must have understood palindrome Linked list. Let's end this video here
722.85 -> If you liked this video, then hit that like button
725.127 -> Subscribe to the channel.
726.527 -> I will meet you in the next one where we will solve more questions of linked list
729.315 -> Will see you in the next one. Till then, bye bye
730.969 ->
Source: https://www.youtube.com/watch?v=ee-DuKtRNGw