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

Problem Link: tinyurl.com/2p869csv
Entire LL Sheet: takeuforward.org/linked-list/...
Check our A2Z DSA Course: takeuforward.org/strivers-a2z...
Please do give us a like, and subscribe to us if you are new to our channel.
Do follow us on our socials: linktr.ee/takeuforward

[@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 😂🤣

[@shubhamrathour9774]

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

[@ManishLakkavatri]

Understood and crystal clear about the solution. Thanks Striver!

[@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;
}
}

[@59_sujatachandra76]

I must say u are the god of DSA .

[@103himajapoluri6]

Hi striver, you always fascinate me with your solutions

[@hareshnayak7302]

Understood,thanks striver for this amazing video.

[@gautamraj-f7d]

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

[@user-bc6ss6gp3z]

#Striver rocks, god bless you & all

[@JothiprakashThangaraj]

understood !!! thanks a lot striver!!!

[@anastasiiamaslova4220]

great explanation!

[@sarangkumarsingh7901]

Awesome Bhaiya........

[@sonakshibajpai6445]

Thank you striver!!

[@adebisisheriff159]

Thanks Striver!!!

[@NazeerBashaShaik]

Understood, thank you.

[@prajjwaldeepghosh7329]

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

[@snehashisratna9074]

Luv you bhai

[@kapiltanwer552]

nice approach compare to all u tube

[@vaibhavgarg5537]

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

[@YourCodeVerse]

Understood✅🔥🔥

[@rahulreddy3588]

Understood sir!😘

[@user-tk2vg5jt3l]

Thank you Bhaiya

[@rushidesai2836]

Nice!

[@saouli1632]

understood dada😃

[@NARUTOUZUMAKI-bk4nx]

Understoood

[@Lucy92735]

Understood!

[@khalasianiket816]

understood❤

[@vivekdarji6440]

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

[@rockstarCoolz]

Understood!!!

[@RoshanKumar-jf5bx]

Understood

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

[@ashishpradhan6250]

understood

[@hat_awesome21]

bro agala vid kab aayegi ?

[@akashkumarprajapati9874]

Bhai linked list ke advance questions lao please

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

[@user-or5oz1pk2x]

I think you should follow A2Z bro

[@user-ku8ou7ys1m]

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

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

[@guttulavybhav1030]

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

[@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;
}

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

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

[@JeniferM-g1q]

its gives time out of bounce and segmentation error

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

[@user-pk1vb6su8g]

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

[@InspireBreeze]

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

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

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

[@iamnoob7593]

US

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

[@user-ul6sh6dj9u]

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.

[@harshnama7059]

one case is not running using your code

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

[@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;
}
}

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

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

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

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

[@user-zy4yh8iw1f]

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

[@user-zy4yh8iw1f]

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

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

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

[@cenacr007]

us

[@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;
}

[@avanishmaurya2034]

Understood

[@abhinanda7049]

understood

[@user-quietwicked]

Understood

[@surbhigupta5777]

Understood

[@himanshidafouty347]

Understood

[@adityapandey23]

Understood

[@hardikpatel352]

Understood

[@abhishekprasad010]

Understood

[@codeman3828]

Understood

[@dewanandkumar8589]

Understood

[@chiragbansod8252]

understood

[@JyotiPrakash-bs9hk]

understood

[@MJBZG]

understood

[@akshayanagelli5962]

understood

[@user-ed8bc2hg5o]

understood