L10. Check if a LinkedList is Palindrome or Not | Multiple Approaches

[@akashkumarprajapati9874]

Aapke chakkar mai maine love babbar chhod diya , you are a god of data structure

[@AbhishekKumar-nz9dn]

same here

[@Ayush37262]

Same, He is good for beginners only!

[@hashcodez757]

bhai vo *chorr diya hota hai🥲

[@sakshammisra189]

@@hashcodez757 bhai tumhe kya pata us bhai ki pohoch kaha tk hai

[@Gamingwithandriyas]

@@sakshammisra189 😂🤣

[@gauravgaurav7927]

No wasting time, straight to the point ! One of the best tutors on internet for DSA.

[@59_sujatachandra76]

I must say u are the god of DSA .

[@Akshay-c8g]

He has done some black magic on DSA

[@RAJADHANISH23BCE984]

​@@Akshay-c8g 😂😂😂😂😂😂😂😂

[@qwarlockz8017]

That was a fantastic explanation. I loved how you took us from brute force to optimized so organically. Thank you.

[@shubhamrathour9774]

Hey Striver you doing such a great job, It's giving us such a huge impact on our professional journey Thanks a lot 🙏

[@selvarajan4062]

Can anyone share the code in Python and java please 😢

[@iamxpossible]

@@selvarajan4062 give the c++ code to chatgpt and ask it to return it in python!!

[@kai125]

14:27 You actually don't need to take the first middle and reverse nodes AFTER the first middle in case of EVEN LL. We can simply take the second middle in both odd and even cases and pass it in the reverse function instead of passing it as middle->next. It will work for the odd LL too because while comparing, both first and second variable will reach the same node as we haven't divided the list. JAVA Code below from LeetCode. /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public boolean isPalindrome(ListNode head) { //Find the middle node. (second middle in case of even no of nodes) ListNode slow = head; ListNode fast = head; while(fast!=null && fast.next!=null){ slow = slow.next; fast = fast.next.next; } // Reverse all nodes starting from the middle node till the last node. ListNode newhead = reverse(slow); // Compare nodes from the original head and from the reversed linked list's head (newhead). ListNode first = head; ListNode second = newhead; //If second reaches null it means we have a palindrome LL. while(second!=null){ if(first.val!=second.val){ //if values not same return false as list is not palindrome. reverse(newhead); //re-reversing the reversed linked list to make it original LL. return false; } first=first.next; second=second.next; } reverse(newhead); return true; } //method to reverse a linked list private ListNode reverse(ListNode head){ ListNode temp = head; ListNode prev = null; while(temp!=null){ ListNode front = temp.next; temp.next = prev; prev = temp; temp = front; } return prev; } }

[@gautamraj-f7d]

CodeHelp ka course kharid ke yaha se padh rha 🙃. Nice explanation.

[@ManishLakkavatri]

Understood and crystal clear about the solution. Thanks Striver!

[@selvarajan4062]

Can anyone share the code in Python and java please 😢

[@luckygarg2294]

@@selvarajan4062 It's on his website

[@dailymix05]

@@selvarajan4062 broo check out the article given below of the video

[@103himajapoluri6]

Hi striver, you always fascinate me with your solutions

[@test-nature]

I have learned that before going to video and ansewer we need our own mind thougts and give a try to solve question. That will help greately. We need to build thought process.

[@Rieshu-l9i]

#Striver rocks, god bless you & all

[@vaibhavgarg5537]

Since we used reverse function within while loop Doesn't the time complexity should be multiplied n/2*n/2..... Please clear this

[@bruvhellnah]

you've probably found your answer by now, but the TC wont be multiplied since the reverse function is not being called for each iteration of the while loop - It is only a one-time operation which immediately returns false thereafter. Hence the O(n/2 + n/2). Also just know that we dont need to reverse the LL back to its original form before returning true/false, it works fine anyway. The TC then would be O(1.5N) instead of O(2N)

[@MAYANKKUMAR-s7v]

DOUBT: At 11:04 , how come node with value 3 from the unreversed linked list portion, point to the (different) node with value 3 from the reversed linked list portion, since node 3 from the reverse linked list portion, already has 1 incoming connection from node 2, and another incoming connection from the node 3, isn't this incorrect, for a singly linked list in c++, we can only have 1 incoming connection and 1 outgoing connection, but for node 3, it has 2 incoming connections?

[@akshaymemane7963]

for a single node, incoming connections can be multiple because the pointers are stored in the nodes from which connection is outgoing. for example: 1->3, 2->3. Both 1 and 2 have their Next pointers pointing to 3. And 3 doesn't have to store incoming pointers. It can store its own outgoing pointer that can point to anything. 3->100, 3->null Hope I explained it well.

[@hareshnayak7302]

Understood,thanks striver for this amazing video.

[@prajjwaldeepghosh7329]

BHAIYA, PLEASE MAKE A VIDEO TO PRINT MATRIX DIAGONALLY. PLEASE. ❤

[@printfiamd5254]

14:58 Why there is a RUNTIME ERROR when I write while (fast->next->next != NULL && fast->next != NULL) instead of while (fast->next != NULL && fast->next->next != NULL)....Please Reply

[@kunalraj2972]

Suppose fast->next = NULL in this case you are looking for fast->next->next which results in run time error.

[@shashwatsingh5129]

The way && operator works is, if the first condition is true, then and only then it moves on the the next condition, if the first itself fails it wont check the next condition, it’s called short circuiting (not sure of the exact term). In your case, had you checked fast.next for null before checking for fast.next.next, the condition would have short circuited on the first check itself and hence it did not have to check for fast.next.next but if you write fast.next.next before the former, the short circuit will never happen and hence the error as fast.next is itself null.

[@saichandu8178]

I am thinkin of different approach. Insert the first half elements to stack and compare the second half elements with the stack. Advantage: Don't have to reverse the list. TC : O(N) SC : O(N/2) -> for the stack space.

[@SAROHY]

just did it with same approch i think but only beat 40% on leetcode i dont understand why also will u share ur code?

[@HarshMishra-hp2lt]

@@SAROHY function call stack used in recursive soln is very optimized because it works at hardware layer directly. But STL stack is very abstract and we don't know what it actually uses underneath to implement stack which might increase the space used by the code.

[@Gurunat16]

Will that not be O(N) + O(N/2). O(N) for LL Traversal (1st half into stack and 2nd half for comparsion) O(N/2) for Stack traversal??

[@brilliantbrains2185]

@@Gurunat16 Yeah you are right .But the main thing is he reduced the space from O(n) [brute] to O(n/2)[his approach]

[@KeepCoding69]

​@@Gurunat16 The TC will be O(N) because we don't need to traverse a stack; we only pop out elements from a stack's top, which takes O(1) time. So for the 2nd half also, the TC is going to be O(N/2) resulting in O(N) total TC.

[@akshaymemane7963]

Something's wrong! here in video: 14:24 For odd numbered linked list example: 1->2->3->2->1->x Once you have reversed the second half, after 2 iterations when you have compared node(1) and node(2) and when your first and second pointer. first ptr will be pointing to 3 but second ptr will be pointing to null. I think you calculated middle wrong. Instead of node(3), it should have been node(2) That way for 3rd iteration your first and second pointers will point to node(3) and we can conclude that LL is palindrome!

[@priyamittal8302]

class Solution { public: ListNode* reverseList(ListNode* node){ ListNode* temp=node; ListNode* prev=NULL; ListNode* curr = temp; if(temp->next == NULL){ return temp; } while(temp != NULL){ curr = temp->next; temp->next=prev; prev=temp; temp=curr; } return prev; } bool isPalindrome(ListNode* head) { if( head==NULL){ return false; } ListNode* revList= reverseList(head); ListNode* head2=revList; while(head != NULL){ if(head->val == head2->val){ head= head->next; head2=head2->next; } else{ return 0; } } return true; } }; Can someone explain why this code is failing at test case [1,1,2,1]?

[@rockstarCoolz]

I am facing same issue....i don't know why.....

[@571_NehaChatterjee]

Shouldn't the space complexity be O(N)? Since we are using recursive stack space?

[@sahilsrivastava7905]

we can also reverse using iterative approach.

[@SHRADDHASAHU-d5v]

@@sahilsrivastava7905 so if we are doing it by iterative approach then space complexity should be O(1), in recursive approach it should be O(n), Right?

[@AlokYadav-ly4ps]

why do we need to reverse the newHead again?

[@thebhagwabilla]

sir you expplain so well, thank you so much sir

[@corporateAniruddha]

Find middle of a Linked list wo bala problem kaha hay vaiya Yeh 10 number video hay usse pehele to nehi hay

[@hat_awesome21]

Follow this link

[@takeUforward]

Aaega jld hi

[@ishikacasley2786]

if we use reverse function in iterative manner so will it increase the time complexity?

[@InspireBreeze]

In iterative approach it will only take O(n) time because the code traverses the entire linked list once, and space complexity of O(1) but in case of recursive approach it will end up taking O(N) because we traverse the linked list twice: once to push the values onto the stack, and once to pop the values and update the linked list. but the space complexity will be O(N) as he explained in the last videos. But i'm also in doubt why he has taken the recursive approach rather than iterative.

[@RahulDeswal-x3u]

I think recursive also taking O(n) here because it is applied on the half part of the linked list

[@InspireBreeze]

@@RahulDeswal-x3u hmm my doubt was regarding the space complexity bcz TC will be same in both the cases. there might be a chance that the stack space it is using is not taking any extra space and have a SC of O(1).

[@ishikacasley2786]

@@InspireBreeze I guess in the case of recursive the space complexity will might vary because usme stack space use hoti hai jitna I know

[@JothiprakashThangaraj]

understood !!! thanks a lot striver!!!

[@sruthimajhi5610]

In the second approach, if the interviewer asks about the time complexity, should we specify it as O(2N) or just O(N) ??

[@kapiltanwer552]

nice approach compare to all u tube

[@mohammadanas7620]

18:55 Pe code likha hai

[@userayush22]

Wy do we need to do re reversal. Can't we directly return false? 16:35

[@paraskashyap7362]

it is good practise to not to alter the input data(the LL might be used somewhere else later, so we must return it un-altered)

[@ajml_hnter]

Simpler bool isPalindrome(ListNode* head) { ListNode *slow = head, *fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; } ListNode *prev = NULL, *current = slow; while(current){ ListNode* next = current->next; current->next = prev; prev = current; current = next; } while(head && prev){ if(head->val != prev->val) return false; head = head->next; prev = prev->next; } return true; }

[@vaarunaramakrishnan6122]

How do you find middle of LL?

[@sarangkumarsingh7901]

Awesome Bhaiya........

[@guttulavybhav1030]

striver you said to take the mid as m1 but it will work in same way even if we take mid as m2....

[@parthh1112]

class Solution { public: void findans(ListNode *&t,ListNode *&y,bool &ans){ if(!t)return ; findans(t->next,y,ans); if(t -> val != y -> val)ans = 0; y = y -> next; } bool isPalindrome(ListNode* head) { bool ans = 1; ListNode *t = head,*y = head; findans(t,y,ans); return ans; } };

[@marveladda9761]

great code ,, literally great

[@VANGAVETISNEHITHA]

Can we solve like we do with strings : reverse the whole linked list and compare it with the original linked list. temp=head if head==None or head.next==None: return head new_head=self.isPalindrome(head.next) front=head.next head.next=front head.next=None return new_head==temp why this is not working

[@vivekdarji6440]

Thank you.. What app are you using in the ipad?

[@JaskaranSingh-hw5jf]

last one can be put down to O(3n/2) with const SC

[@anastasiiamaslova4220]

great explanation!

[@teamamroninja333]

slow->NEXT FOR REVERSING IS WRONG WILL FAIL IN TEST CASES USE ONLY SLOW, FOR REVERSING

[@sonakshibajpai6445]

Thank you striver!!

[@mathsworldbysuraj6278]

use iterative method as recursion takes (N/2) space

[@deepakvarma473]

Hey All , A quick doubt , When finding the middle of the linked list , wont the time complexity be O(N) and not O(N/2) because fast pointer will have to reach the end of the linked list for us to get the slow or middle node ? Correct me if i am wrong

[@saivamsi8400]

Bro, U need to consider the number of iterations u hav taken to reach the last node but not the number of nodes you have crossed while calculating time complexity

[@procrastinator0811]

why not reverse the entire linked list and compare with original by saving values in 2 variable respectively for front and back traversal ?

[@RavikantMunda]

When you reverse the whole linked list, then you can't access the previous(original) head, which is now the last node of the new Linked List. if list1 = 1 -> 2 -> 3 -> 4 then on reversal list1 = 4 -> 3 -> 2 -> 1

[@procrastinator0811]

@@RavikantMunda i will traverse the list twice ...in first iteration will store the elemensts in a string for forward traversal . then will reverse the LL and traverse and store the elem as string as backward traversal . now will compare both the string and return . TC -> O(2*n)

[@RavikantMunda]

@@procrastinator0811 We have already implemented a O(n) space solution in form of stack, so we need to improve on space with this solution

[@adebisisheriff159]

Thanks Striver!!!

[@hat_awesome21]

bro agala vid kab aayegi ?

[@harshnama7059]

one case is not running using your code

[@om3478]

watch lecture 13 of this playlist to find middle of LL.

[@ajjupandey5742]

Sriver Bhai just wanted to ask currently I am in semester 5 and want to prepare for DSA in python i studied DSA in sem 3 but for University exam so I should follow ur A2Z playlist or SDE sheet please reply brother

[@DeepakPatel-d5v]

I think you should follow A2Z bro

[@selvarajan4062]

Can anyone share the code in Python and java please 😢

[@mohitt_parmar]

using stack 2:08

[@YourCodeVerse]

Understood✅🔥🔥

[@AkOp-bf9vm]

tortoise and hare algo is in lecture number 13

[@rahulreddy3588]

Understood sir!😘

[@ritikrawat2447]

Isn't my solution easy and good ? , i just do simple iteration slow and fast and reverse the first half of the linkedlist while finding the mid point and after that just check the reversed linkedlist and the slow.next linkedlist . public boolean isPalindrome(ListNode head) { ListNode slow = head, fast = head, prev = null , temp = null; while (fast != null && fast.next != null) { temp = prev; prev = new ListNode(slow.val); prev.next = temp; slow = slow.next; fast = fast.next.next; } // This condition for odd length if ( fast != null ) { slow = slow.next; } while ( slow != null && prev != null ){ if ( prev.val != slow.val ){ return false; } slow = slow.next; prev = prev.next; } return true; }

[@piyush.28]

This code is more readable

[@kartiksinghora251]

The test case 1,0,0 is not working how to fix this

[@elite.warrior]

class Solution { public ListNode reverse(ListNode slow,ListNode tail){ ListNode prev = null; while(tail != null){ ListNode front = tail.next; tail.next = prev; prev = tail; tail = front; } return prev; } public boolean isPalindrome(ListNode head) { if(head == null || head.next == null)return true; ListNode slow = head, fast = head; while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; } ListNode tail = slow; tail = reverse(slow,tail); ListNode temp = head; while(temp != slow){// or tail !=null if(tail.val != temp.val) return false; tail = tail.next; temp = temp.next; } return true; } }

[@JeniferM-g1q]

its gives time out of bounce and segmentation error

[@snehashisratna9074]

Luv you bhai

[@selvarajan4062]

Can anyone share the code in Python and java please 😢

[@Gokul-gkl]

*** off

[@NazeerBashaShaik]

Understood, thank you.

[@satyamjaiswal7419]

i think we can just reverse whole node then compare it to original one it will be simple.

[@mehulgarg7253]

It include space complexity of O(n) bro because of one you reverse whole LL then from which LL you compare your new reversed LL

[@dhakerk094]

sir appne niche linked lisk vapas reverse to kr di but first half se connect nhi kru aisa kyo please explain anyone to me

[@takeUforward]

kyu ki kbhi tode hi nai the na bro

[@swagcoder]

I think the space complexity should be O(n) as we are using the Linked List itself to check if palindrome or not(performing operatins on LL). In that case the TC and SC is equivalent to the brute force and the brute one is easier to understand and implement. Please clarify!

[@AyushVachhani]

Hey buddy, just to clear your doubt, the Space complexity is only counted, if we create a new data structure, if we modify an data structure in place(i.e the one that was given in the question, then it is not counted in space complexity)

[@swagcoder]

Hi , but in other lectures of striver, he has mentioned many times that if you tamper the given input it’s counted, so got a bit confused

[@AyushVachhani]

@@swagcoder Hey, I think, there might be some misunderstanding, I would suggest that you don't consider it as space complexity in this context.

[@akashkumarprajapati9874]

Bhai linked list ke advance questions lao please

[@saouli1632]

understood dada😃

[@gautamsaxena4647]

understood bhaiya

[@trushitpatel9965]

```Java class Solution { public boolean isPalindrome(ListNode head) { String num = ""; ListNode curr = head; while(curr != null){ num = num + curr.val; curr = curr.next; } int i = 0, j = num.length() - 1; while(i < j){ if(num.charAt(i++) != num.charAt(j--)) return false; } return true; } } ``` How come this O(1.5N) is not better than this? plz someone explain?

[@DeadPoolx1712]

UNDERSTOOD;

[@Learnprogramming-q7f]

Thank you Bhaiya

[@rushidesai2836]

Nice!

[@khalasianiket816]

understood❤

[@random-xl3zm]

Striver just wanted to ask i havent started dsa so sud i start from that a2z dsa playlist along with the takeuforwsrd website where all the marerial is there So can i staet following it sequence wise I have already done cs50x from harvard so i thought lets begin dsa for interviews now Nd i dont know dp lec 34 or 35 is in the middle of othee series pls check that once does it really belong there Also is all the dsa topics covered in that playlist bcz i m newbie here And if not also it will b nice if u cud make a vdo as to what topics tocover other then that a2z playlist for dsa from which sources bcz for begineer its tough to find really good resources on dsa bcz many people will waste our time on the name of teaching dsa so i want from u the sources where i can get genuine dsa lec of the topics not covered

[@takeUforward]

it does not needs dp knowledge, it is solved without dp

[@AdityaJain-ed9my]

thanks sir.

[@hitmanop4078]

Watched !!!

[@adityabahulikar3270]

Can someone give me code in python

[@Lucy92735]

Understood!

[@NARUTOUZUMAKI-bk4nx]

Understoood

[@biplabmondal1891]

Why he is called Striver

[@nehabharti_1750]

Because he strived unlike anything to achieve what he is today & through this work of his, he not just inspires and motivates us....but also actually helps us in our journey to success. He is someone who has strived to rise right from the ashes and turned out to be so strong and phenomenal. Respect in the power of e!!!! P.S: He is still striving today....I mean look at the amount of (optimal quality)work he renders everyday!!!

[@studyah]

understood!!!

[@yash9725]

Node* reverse(Node *head) { Node *pre = NULL; Node *cur = head; while(cur != NULL) { Node *post = cur->next; cur->next = pre; pre = cur; cur = post; } return pre; } Node *findMiddle(Node *head) { Node *slow = head, *fast = head; while(fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; } bool isPalindrome(Node *head) { if(head == NULL || head->next == NULL) { return true; } Node *mid = findMiddle(head); Node *newHead = reverse(mid); while(head != NULL && newHead != NULL) { if(head->data != newHead->data) { return false; } head = head->next; newHead = newHead->next; } return true; }

[@RoshanKumar-jf5bx]

Understood

[@chiragbansod8252]

understood

[@ajaymishra1511]

cant we just convert it into a double link list and then use 2 pointer on it

[@iamnoob7593]

US

[@SamyakSharma-oy1bv]

respect ++;

[@cenacr007]

us

[@nishant4595]

understood!!!

[@rockstarCoolz]

Understood!!!

[@avanishmaurya2034]

Understood

[@abhinanda7049]

understood

[@rajatshukla2605]

Understood!

[@user-quietwicked]

Understood

[@akshayanagelli5962]

understood

[@codeman3828]

Understood

[@ashishpradhan6250]

understood

[@hardikpatel352]

Understood

[@JyotiPrakash-bs9hk]

understood

[@dewanandkumar8589]

Understood

[@MJBZG]

understood

[@abhishekprasad010]

Understood

[@YPZanzarukiya]

understood