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...
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; } }
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.
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 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.
@@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?
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 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).
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!
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
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
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)
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; }
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
```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?
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.
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)
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
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.
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
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!!!
