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

Please do give us a like, and subscribe to us if you are new to our channel.

[akashkumarprajapati]

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

[gauravgaurav]

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

[kai]

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

[shubhamrathour]

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

[qwarlockz]

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

[gautamraj-fd]

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

[ManishLakkavatri]

Understood and crystal clear about the solution. Thanks Striver!

[himajapoluri]

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-li]

#Striver rocks, god bless you & all

[vaibhavgarg]

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

[MAYANKKUMAR-sv]

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?

[hareshnayak]

Understood, thanks striver for this amazing video.

[prajjwaldeepghosh]

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

[printfiamd]

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

[saichandu]

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.

[akshaymemane]

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!

[priyamittal]

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]?

[_NehaChatterjee]

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

[thebhagwabilla]

sir you expplain so well, thank you so much sir