L12. Find the intersection point of Y LinkedList
ฝัง
- เผยแพร่เมื่อ 5 ก.พ. 2025
- Problem Link: tinyurl.com/yc...
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...
intuation behind the optimal approach🔥🔥, legend ....
Best video for this problem on youtube till date. Covered everything from brute-force to the best-optimised way to solve this problem. Kudos Striver!! Enjoying this path and the playlist.
Sir you, covers brute-force, optimized approaches, and even a killer third option! Well done, keep up the good work!
A big salute to striver and his third approach 🫡
You need to be a superhuman to discover the third approach on your own! Thankssssss alloooooottt striver 😇
Quality content brother I was waiting for Linkedlist God bless you brother
saw many videos to understand the 3rd approach but then landed on this video which has ended by search.thank u stiver for brilliant explanation.
The last algorithm man. After learning about it, it feels like why I didn't I think about that possibility. Thank you Striver for such a great explanation.👌👌
optimal approach just GENIUS!! hats off captain!!
Timestamps
Hashing Approach - 1:20
Length Difference Approach : 8:10
Optimal Approach- 16:25
Aayla Jaado in 3rd approach Maja arha hai ab problems krne m . Thanks striver bhaiya for delivering such approaches things gets better and understandable ❤
salute for optimal approach 🔥
Beautiful Optimal approach. Thanks Striver!
the optimal approach is 🔥
teachers like him comes in a decade or more, bhaiya please try to upload stacks and queues and strings as well
The hashing one can be done in one iteration as well. We can insert in map acc to both LL at once. And check at that moment only if the freq is >1.
Code - C++
int intersectPoint(Node* head1, Node* head2) {
Node*p1=head1;
Node*p2=head2;
unordered_map hashmap;
while(p1||p2)
{
if(p1) hashmap[p1]++;
if(p2) hashmap[p2]++;
if(hashmap[p1]>1) return p1->data;
if(hashmap[p2]>1) return p2->data;
p2=p2->next;
p1=p1->next;
}
return -1;
}
but it takes more space complexity while the last solution of Striver only takes O(1)
you are returning the data integer not the node
After following playlist till here, now i'm able to do these question myself 🌚
Thank You Striver Bhaiya!!!
Bro how are you able to think the approach and till which approach could you think of like till brute better or optimal and how?
i was able to solve bruteforce but the 2nd and 3rd approches were out of my mind☹☹@@navneetuppal9753
Thank you Striver for explaining so well...
third approach literally blown my mind
"literally"
Understood.....Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Wow Just wow what a mind blowing approch striver , Cool.thanks for this amazing video.
the way you explain the concepts is lit🔥
the main challenge I found while solving DSA questions is that I am not able to find out approach to solve. In majority of cases when you told me the approach I can then easily solve that question without problem. If you are reading this please tell me How can I train myself so that I can easily understood the approach ?? I JUST NEED THE APPROACH AND THE REST IS EASY.
Thank you for the approaches.
Thank you striver !!
The thing which has hitted my head is that start both the linked list at a same time and move them equally if
First ll comes to end the return second ll
If first ll =second ll return any linked list
If second comes to end return first
Thank you bro!💙
keep teaching like this💯🤗
amazing solution!
third approach is the real goat
Third approach is mind blowing
zeherrrrrrr teaching
thanks bhaiya for providing such an amazing content
damnn🔥🔥the third approach!!!
striver can we expect stack and queue from u next ?
Yes please
String much needed
Stack and queue already there
😢
Thanks sir
Last one is 🔥🔥
Thankyou so much for great explanation @Striver
mind blowing method. cant believe woahh
great explanation!
third approach is like forming loop using junction and making them collide op approach🔥
NICE LECTURE AND PLZ UPLOAD REMAINING LECTURES OF A TO Z SDA SHEET PLZ THEY ARE VERY HELPFULL FOR US
damn man! what an idea for the optimal approach
Done it in 5 lines:
Node* first=head1;Node* second=head2;
while(first!=second){
first=(first!=NULL) ? first->next : head2;
second=(second!=NULL) ? second->next : head1;
}
return first;
3rd approach was a 🤯🤯
Understood✅🔥🔥
Nice teaching
So help full video
Why the time complexity of the last approach is not O(2 * (n1 + n2)) ??
Same doubt
@@BhavanaReddy15 because you're traversing both linked list simultaneously not separately.
for example while traversing first linked list you traverse m step and reach null then traverse at maximum n step at worst case when there's no match and simultaneously you're traversing through the other linked list first n step and then m step at worst case when no match so the complexity is O(m+n)
damn the third approach is beautiful
beautiful
Lecture successfully completed on 28/11/2024 🔥🔥
Understood.🎉❤
Understood 😊
Understood 👏
The first time who have invented this algo must be from another dimension😙
dimag hil gya bhai 🤐🤐
3rd approach was awesome haha
thank you man
I have a doubt, when both the linked lists dont have a intersection point, the while loop should run forever right?, because we reassign if pointers reaches null, so the pointers wont be reaching null so they wont become equal right ? then how the loop stops?
i have taken a course of dsa and in that course one teacher tell the 2 approach till this date I think this approach is optimized but today (wake up to reality ho gaya)
understood ❤
Thank you so much!!
UNDERSTOOD;
Was asked to me in Oracle Intern Technical Round 1 Interview
Understand 31:53
Understood, thank you.
Understood!
Thanks a lot bhaiya
can we do like reverse both ll and then check them until they are equal ..once unequal return the prev node
Thank you Bhaiya
hey!!
what if we start traversing from end of the both list and return the last node where they are equal??
thank you striver
Node* findIntersection(Node *firstHead, Node *secondHead)
{
//Write your code here
Node* t1=firstHead;
Node* t2=secondHead;
while(t1!=NULL && t2!=NULL)//when both are null
{
t1=t1->next;
t2= t2->next;
if(t1== t2) return t1;
if(t1 == NULL) t1=secondHead;
if(t2==NULL) t2=firstHead;
}
return nullptr;
}this is best I think
understood!!!
Understooood
In 2nd approch when N1 > N2 then in collision funtion we have to bring the t1 at alin postion which matches the t2 but the code is just work for when N1 < N2 ??
if anyone does figure out the third approach on his own, he is a genius.........
me
Please correct me if I'm wrong. If the two linked lists are never intersecting and are of different lengths, this will be a infinite loop because t1 will never be equal to t2 and we'll keep on interchanging them with heads in case of null
Bro even if they are non-touching, after the first exchange for both they will come in parallel so the loop will terminate when they reach null together
@@shivangairan6904 Understood. Thanks
in the second approach - what if the length of both the linked lists is same? how will the collision function work then?
The difference will be 0. So basically it starts comparing from the head only and then simultaneously incrementing until common node is reached
how does storing nodes directly make difference if we encounter same node value form second linked list why hashmap was showing no???/
Hey Striver, for the last algorithm, wouldn't it work too if when T1 or T2 reach NULL , they can be put back to Head1 or Head2 respectively? T1 goes back to Head1 and T2 goes back to Head2, it's working the same.
Try with different example like N1=5 & N2= 7, then you will get to know why it fails
why use this line mpp.find( temp) != mpp.end(); please explain this line
!= use why
thanks
My simple java code
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode temp1=headA;
ListNode temp2=headB;
while(temp1!=temp2){
if(temp1==null){
temp1=headB;
temp2=temp2.next;
}
else if(temp2==null){
temp2=headA;
temp1=temp1.next;
}
else{
temp1=temp1.next;
temp2=temp2.next;
}
}
return temp1;
}
}
can we even compare each node of one LL to Other LL and get the first intersection ??
that's brute force approch..still works but time complexicity will be of O(n^2).here we will get in O(max(len(t1),len(t2)) + distance of intersection from smallest LL)....somewhat linear complexity
anyone pls answer in second approach what happens if t1 and t2 contains same element before linking?
No problem in that case too bro.. cause we are comparing the pointers themselves (whether they point at same position/node or not),not their values..
Hope this helps..
@@qwerty20917 thank you bro
pls can anyone explain me what is the difference in storing a node in hashmap and a value ? if the same value is present in second LL also why doesnot it indicate yes? pls give me hintts...
Because Node is a class which consists of the address of the data too. Hence while comparing the same value, we are not checking if it's in the same address, so we can't conclude on that. So to check if it's in the same address, we compare the whole Node and not just the value.
@@lot2say590 Thanks bro same question arise to me
in this code if you remove the if t1==t2 return t1, it should work fine right? Because the while loop will break in case both of them become equal, but the problem is, removing this condition will cause an error to appear. Can someone please answer this issue. Thanks
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p1 = headA, *p2 = headB;
while(p1 != p2){
p1 = (p1 ? p1->next : headB);
p2 = (p2 ? p2->next : headA);
}
return p1;
}
Bro thanks
understood!
understood
Why wasn't a set used in the hashing approach? Wouldn't that be better?
That will still take O(n) space
node* intersectionY(node* head1, node* head2) {
if (head1 == NULL || head2 == NULL) return NULL;
node* temp = head1;
map mpp;
// Insert nodes of the first linked list into the map
while (temp != NULL) {
mpp[temp] = 1;
temp = temp->next;
}
// Traverse the second linked list and check for intersection
temp = head2;
while (temp != NULL) {
if (mpp.find(temp) != mpp.end()) {
return temp;
}
temp = temp->next;
}
return NULL;
}
int main()
{
vector arr={3,1,4,6,2};
vector b={1,2,4,5,4,6,2};
node *head1=convertarrtoLL(arr);
node* head2=convertarrtoLL(b);
node* head=intersectionY(head1,head2);
cout
Understood
small correction
if (n1 < n2) {
return collisionPoint(headB, headA, n2 - n1);
} else {
return collisionPoint(headA, headB, n1 - n2);
}
baaki first class
understood.
please share the code for last approach
is circular linked list important?...if yes,from where to do..someone pls suggest
mapm;
while(headA!=nullptr)
{
m[headA]++;
headA=headA->next;
}
while(headB!=nullptr)
{
if(m.find(headB)!=m.end())
{
return headB;
}
headB=headB->next;
}
return nullptr;
waatha idhan da coding 🤯🤯
SUUUUUUUUPERRRRRRRRRBBBBBBBBBBB