L10. Check if a LinkedList is Palindrome or Not | Multiple Approaches
Вставка
- Опубліковано 10 вер 2024
- Problem Link: tinyurl.com/2p...
Entire LL Sheet: takeuforward.o...
Check our A2Z DSA Course: takeuforward.o...
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/take...
Aapke chakkar mai maine love babbar chhod diya , you are a god of data structure
same here
Same, He is good for beginners only!
bhai vo *chorr diya hota hai🥲
@@hashcodez757 bhai tumhe kya pata us bhai ki pohoch kaha tk hai
@@sakshammisra189 😂🤣
That was a fantastic explanation. I loved how you took us from brute force to optimized so organically. Thank you.
I must say u are the god of DSA .
He has done some black magic on DSA
Hey Striver you doing such a great job, It's giving us such a huge impact on our professional journey
Thanks a lot 🙏
Can anyone share the code in Python and java please 😢
CodeHelp ka course kharid ke yaha se padh rha 🙃. Nice explanation.
Understood and crystal clear about the solution. Thanks Striver!
Can anyone share the code in Python and java please 😢
Since we used reverse function within while loop
Doesn't the time complexity should be multiplied n/2*n/2.....
Please clear this
Hi striver, you always fascinate me with your solutions
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;
}
}
BHAIYA, PLEASE MAKE A VIDEO TO PRINT MATRIX DIAGONALLY. PLEASE. ❤
Understood
#Striver rocks, god bless you & all
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.
just did it with same approch i think but only beat 40% on leetcode i dont understand why
also will u share ur code?
@@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.
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??
@@Gurunat16 Yeah you are right .But the main thing is he reduced the space from O(n) [brute] to O(n/2)[his approach]
Understood,thanks striver for this amazing video.
Shouldn't the space complexity be O(N)? Since we are using recursive stack space?
we can also reverse using iterative approach.
@@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?
Find middle of a Linked list wo bala problem kaha hay vaiya
Yeh 10 number video hay usse pehele to nehi hay
Follow this link
Aaega jld hi
if we use reverse function in iterative manner so will it increase the time complexity?
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.
I think recursive also taking O(n) here because it is applied on the half part of the linked list
@@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).
@@InspireBreeze I guess in the case of recursive the space complexity will might vary because usme stack space use hoti hai jitna I know
understood!!!
Thank you striver!!
understood !!! thanks a lot striver!!!
Watched !!!
Understood, thank you.
understood
Awesome Bhaiya........
Thanks Striver!!!
nice approach compare to all u tube
The test case 1,0,0 is not working how to fix this
last one can be put down to O(3n/2) with const SC
Luv you bhai
thanks sir.
Can anyone share the code in Python and java please 😢
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?
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.
Thank you Bhaiya
Understood sir!😘
Understood!
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;
}
great explanation!
tortoise and hare algo is in lecture number 13
Understood✅🔥🔥
Understoood
using stack 2:08
understood❤
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
striver you said to take the mid as m1 but it will work in same way even if we take mid as m2....
Thank you..
What app are you using in the ipad?
Nice!
understood dada😃
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
I think you should follow A2Z bro
Can anyone share the code in Python and java please 😢
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
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
why not reverse the entire linked list and compare with original by saving values in 2 variable respectively for front and back traversal ?
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
@@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)
@@procrastinator0811 We have already implemented a O(n) space solution in form of stack, so we need to improve on space with this solution
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!
Wy do we need to do re reversal. Can't we directly return false? 16:35
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)
Bhai linked list ke advance questions lao please
bro agala vid kab aayegi ?
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
it does not needs dp knowledge, it is solved without dp
its gives time out of bounce and segmentation error
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
Suppose fast->next = NULL in this case you are looking for fast->next->next which results in run time error.
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.
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;
}
};
great code ,, literally great
sir appne niche linked lisk vapas reverse to kr di but first half se connect nhi kru aisa kyo please explain anyone to me
kyu ki kbhi tode hi nai the na bro
```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?
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;
}
This code is more readable
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]?
I am facing same issue....i don't know why.....
one case is not running using your code
US
i think we can just reverse whole node then compare it to original one it will be simple.
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
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;
}
}
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!
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)
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
@@swagcoder Hey, I think, there might be some misunderstanding, I would suggest that you don't consider it as space complexity in this context.
Why he is called Striver
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!!!
us
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;
}
Understood
understood!!!
understood
Understood!!!
Understood
Understood
Understood
Understood
Understood
understood
understood
Understood
Understood
Understood
Understood
Understood
Understood
Understood
understood
understood
understood