Intersection point of two Linked Lists | Amazon | Microsoft | Brute | Better | Optimal1 | Optimal2

[@takeUforward]

Understooooooooooooooood? . Instagram(connect to know closely about updates): instagram.com/striver_79/ . . If you appreciate the channel's work, you can join the family: bit.ly/joinFamily

[@sagardas4569]

Your voice has changed i think...

[@gautamsuthar4143]

11:01 How is it O(M). It should be O(M+N) according to me because we can't traverse both pointers simultaneously. Please reply

[@dennyage4791]

Understood

[@nullvoid7543]

Yesss sir

[@rahulnegi4027]

thanks bhaiya

[@subirkumar6786]

Brute approach - 1:23 Better approach - 3:04 Optimal 1 - 7:15 Optimal 2 - 12:05

[@p61800]

Thanks for this explanation! Please don't stop this ever, best thing on Internet.

[@takeUforward]

Glad :)

[@anupamayadav7038]

best explaination ... Linkedlist was a kind of nightmare for me but now your tutorials are making it is easy ..and simple for me. Thankyou.

[@RV-qf1iz]

I liked the hashing approach as it is very easy to code:- public ListNode getIntersectionNode(ListNode headA, ListNode headB) { Mapmap=new HashMap(); ListNode t1=headA; while(t1!=null){ map.put(t1,t1.val); t1=t1.next; } ListNode t2=headB; while(t2!=null){ if(map.containsKey(t2)){return t2;} t2=t2.next; } return null; }

[@anurondas3853]

Sadly it may not be the case with the interviewer.

[@RV-qf1iz]

@@anurondas3853 why we cannot use hashmap in an interview ?

[@pranav288]

@@RV-qf1iz extra space is not good

[@jatinukey4062]

​@@RV-qf1izthey will ask to optimize the space complexity 😅

[@_-6912]

I'm happy actually, first best solution was something even I came up the first time when I was doing this question.

[@omhari8297]

Thanks for the video... One more approach if we are allowed to change the value of nodes:- ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *x=headA; while(x!=NULL) { x->val=x->val-1000'000'001; x=x->next; } ListNode *ans=NULL, *y=headB; while(y!=NULL) { if(y->valnext; } x=headA; while(x!=NULL) x->val+=1000'000'001, x=x->next; return ans; }

[@JyotiSharma-wb1vy]

Wow, this video is pure gold! 🌟 One of the best explanations I've come across, and it's not just about the brute force to optimized approach, but also the deep intuition behind it. I absolutely loved it! 👏 Thanks for breaking it down so clearly!

[@abhay9994]

I wanted to send you a heartfelt thank you for your tireless dedication to teaching DSA for free. Your selflessness and passion for helping students with their job interview preparation have made a significant impact on my life and countless others. I am incredibly grateful for the knowledge and confidence you have imparted to us. Thank you for everything you do!❣✨✨

[@paragsaini2795]

Another approach we can try is Just make tail_node -> next, points to one of the head, and now the problem reduce to the detecting the cycle in linked list. And at last modify tail_node->next to nullptr to obtain the original linked lists

[@yatinarora1252]

In this question there is mentioned there is no cycle in linked list

[@justarandomguy6106]

Good observation

[@virusnetic]

@@yatinarora1252 you can just make a cycle by updating tail_of_first_ll.next = head_of_first_ll and revert it back.

[@himanshumaurya428]

@@virusnetic you are not allowed to change the structure of LL.

[@sourabhkumar5815]

That's a very creative approach. but it won't cover the case when there is no merge point.

[@dipakraut6058]

The second approach was just Amazing.

[@jaskiratsinghosahan4638]

Best DSA series on whole KZbin🔥🔥

[@joydeb8202]

Love your Videos............ Following this series since 2weeks .......... You are inspiration dude..... ; ) Get well sooooooooon...waiting for your comeback... take rest

[@lokeshvikram6192]

You are helping me a lot to get trained for placements bro. I am waiting for your next videos.i would be happy if you could complete this placement series as soon as you can because iam following your SDE sheet only bro.

[@pranav288]

hey did only doing sde sheet work for you ? how was your interview experience ?

[@Paul_atredis]

@@pranav288 well he didn't replied but what about you? did the sheet helped you?

[@pranav288]

@@Paul_atredis I cracked the very first interview I appeared for. Still looking for more opportunities, will keep you posted.

[@abhivarma1756]

@@pranav288 update please

[@viveksingh_01]

@@pranav288 any updates?

[@mahithareddymaram4516]

The explanation is super easy to understand. Thanks !! keep up the good work

[@positivity5358]

I don't know why but I really like your voice 😍( with that bengali accent touch).... Can't tell about the content where you teach because I am in 12th standard only 😉...But I know you are doing great things to make a remarkable change in college student by shaping their carrier...I know you have a job but you are selfless enough to guide students....Kudos to you bhaiya...

[@takeUforward]

But am not a bengali XD

[@positivity5358]

@@takeUforward I know that well but still that could be because you may have lived in Bengal that why....🙂🙂

[@AditiPawar-u5q]

wow!!!!!! Amazing solutions. I hope one day I will be able to solve like this.

[@ranasauravsingh]

UNDERSTOOD... !!! Thanks, striver for the video... :)

[@techykush7192]

wow amazing explanation love u bhaiya keep it up thanks a lot 😍😍

[@toshanverma1084]

second approach is just wow. Thankyou.

[@bhaveshkumar6842]

Correct me if I'm wrong. The hashing solution will have a space complexity of O(m+n). We have to consider the case where there's no intersection. So, we will add the addresses of all the nodes of the first list to the hash set and we will also have to add the addresses of all the nodes of the second list to the set since there is no common node.

[@anshumaan1024]

no, simply store the all nodes of first list, for second list you don't need to store the nodes, simply traverse each node of second list and check if they were in the hash table or not, if the node of second list is already in the set then, it means it the intersecting node, So, TC-> O(m+n) SC -> O( m), if m is the size of first list

[@nishantingle1438]

Best thing is the explanation rather than the code. You're awesome.

[@rishikeshpawar3230]

Thanks !! Great explanation. Though I think among optimized approaches #1 and #2, the #1 is would be faster, as traversing each of linked list once only. For #2, your are traversing both lists, twice.. Still the #2 intuition was great.

[@ayushshukla1597]

Even the interviewer would not know about the 2nd Optimal Solution. Amazing work.

[@savalalingeshreddy6750]

thanks for the video bro good explanation keep doing!!! 3 methods--- {1}-1st Method- --------------- #include #include using namespace std; void insertFront(int d); struct Node{ int data; Node *next; Node(int x){ data = x; next = NULL; } }; Node* insertEnd(vector a,Node *head){ struct Node *dup = NULL; for(int i=0;inext = temp; dup = temp; } return head; } Node *intersectionOfLinkedList(Node *h1,Node *h2){ Node *temp = h2; while(h1 != NULL){ while(h2 != NULL){ if(h1 == h2) return h1; h2 = h2->next; } h1 = h1->next; h2 = temp; } return h1; } int main(){ struct Node *head1 = NULL; struct Node *head2 = NULL; vector a{1,3,4,5,6,7,187}; vector b{34,3,54,67,6,6,6,234}; head1 = insertEnd(a,head1); head2 = insertEnd(b,head2); Node *p = head2; Node *hd1 = head1; Node *temp = NULL; while(head1 != NULL){ if(head1->data == 3){ temp = head1; break; } head1 = head1->next; } while(head2->next != NULL) head2 = head2->next; head2->next = temp; Node *ans = intersectionOfLinkedList(hd1,p); cout

[@manikanth.8507]

Great Work

[@pendyalaabhishek8866]

i have a doubt in second why will both linked list have a node at same address ? it is possible that only the intersection vales are same but address is different so that mean 2nd method is wrong . ex 1->2->3->4->5->NULL; 10->11->3->4->5->NULL; if we take these 2 linked lists 3->4->5->NULL is the intersection but node 3 will have different address in both of the lists so 2nd method is wrong .

[@Jack-mc7qe]

@@pendyalaabhishek8866 nope we dont have to separate nodes having same values we have to separate nodes with same address and on the top of that if their addresses are same then their values will also be same But its possible to have same values at 2 diff address but that wont be intersection point

[@joseph2073]

legend dude

[@reassume4826]

Mind-blowing moment @13:17

[@ДенисМ-д7ъ]

The best explanation. Thank you

[@surajsarmahpathak926]

Very imp concept. Thanks Striver !

[@oqant0424]

after your hint i coded it myself..your logic explanation is very gd

[@jitendrapal4216]

Your explanation is great ❤

[@aditinagda6609]

One of the approach could be to create a set of Nodes, place first linkedlist nodes into that set, then start traversing the second linkedlist, the moment, we find set already contains that node, we return that node. And in the very last simply return the null.

[@jatinukey4062]

Yeah this approach will work also

[@kaushikramabhotla4635]

the second optimal approach is 🔥🔥 !!! aag laga di bhai :)

[@jatinkumar4410]

Amazing approach, amazing explanation

[@udayjordan4262]

basically you can also use hashmap if interviewer doesnt ask you space optimize it more .i mean constant space.

[@pranshumehta3228]

Time complexity of 2nd optimal solution would be O(m+n) in worst case Isn't it?

[@hariprasadsa8263]

In Optimal 2 Answer I was astonished by the way you have shown us to solve...Keep going man!

[@alokkumar-ki7wp]

Love you Striver!! What a code that was of 2nd optimal solution.

[@hackpiece3094]

Thank you so much ❤️ Keep up the good work brother😁

[@kaichang8186]

understood, thanks for the detail explanation

[@oqant0424]

THANKS VAEYA..EXPLAINED IT REALLY WELL..I WAS STUCK AT THIS PROBLEM FOR 3 DAYS...SAW MANY VIDEOS.....GOT NOTHING..THEN SAW YOUR VIDEO...GOT EVERY THING ..AND MOST IMPORTANTLY WHERE I WAS MAKING ERROR...THANK U SO MUCH VAEYA FROM THE BOTTOM OF MY HEART

[@ShaikSharma]

i have my accolite interview today hoping the best

[@vidhi_bhatt]

Beautifully explained!!

[@adityan5302]

Python Solution: l1, l2 = head1, head2 while l1!=l2: if l1==None: l1=head2 if l2==None: l2=head1 l1=l1.next l2=l2.next return l1.data

[@jaswantrohila3776]

What a solution 🔥🔥 didn't thought of this....thanks

[@factfactorial632]

Great Explanation Bhaiya I think TC of last solution should be O(m+n) correct me if I am wrong

[@manistrikes]

No ,consider 2 linked list which are not intersecting...then u would had to traverse the bigger list twice in that case ...so the TC is 2×m

[@prestoX]

Beautiful explanation.

[@calmyourmind5617]

" Obviously the interviewer will not be happy and he will ask you to optimize the approach" - has a separate fanbase.

[@venkatsaireddy1412]

I like the technique♥

[@krishnavamsichinnapareddy]

Superb explanation ❤

[@yogeshvaishnav6464]

Striver! I didn't get one thing in the 2nd best approach... How did this loop breaks when there is not intersection point and list1 is shorter than list2? while(a != b){ a = (a == NULL) ? head2 : a->next; b = (b == NULl) ? head1 : b->next; } why didn't this go to infinite loop? as a and b gets interchanged on reaching NULL and starting it all over again but from the other list this time.

[@yogeshvaishnav6464]

Okay got this! At one point both becomes of same length and head towards the intersection point (or NULL if there is no intersection). Thanks for the video. dudho nahao futo falo !😂

[@takeUforward]

They will start moving together and they will reach null at sane time. Take an example u will understand. If they reach null at same time, its over.

[@anchitmittal6546]

Very Well Explained. Thanks Mate 👍

[@gautamsuthar4143]

11:01 How is it O(M). It should be O(M+N) according to me because we can't traverse both pointers simultaneously. Please reply.

[@chowmein1397]

It will be O(M) if M>N, else it will be of O(N) We can traverse both of them together by using if conditions in loop while(temp1!=NULL || temp2!=NULL) { if(temp1!=NULL) { l1++; temp1=temp1->next; } if(temp2!=NULL) { l2++; temp2=temp2->next; } } temp1 and temp2 are dummy nodes of list 1 and list 2

[@gautamsuthar4143]

@@chowmein1397 thanks. I appreciate it.

[@shreyasingh1258]

The way you explain really helps alott!!!thanks bhaiya🙌

[@takeUforward]

Glad to hear that

[@_hulk748]

understood sir ji🙏🙏

[@Ashwani_sharma]

Last approach will not work when no intersection, stuck in while loop

[@starboy415]

if(a==NULL && b==NULL) return -1; add this statement at the last in the while loop and it should work

[@paragroy5359]

Nice explanation sir......thanks for the playlist extremely helpful...

[@way2prosperity]

when will the loop break if the linked lists don't intersect according to best optimal 2nd solution? the condition d1!=d2 in while loop, will it result in an infinite loop in this case? i cant understand. will you explain?

[@heysitam]

Thankyou vaiya for such an awesome explanation

[@shivyanshgarg]

What if we reverse the linked list and then traverse until both the nodes are same, and as soon as they are different, we output the previous node? Can anybody tell about this approach?

[@dhirenparekh2646]

It is not good because for case 1: where you are reversing the list by changing the next pointer of each node to previous. Here as you are modifying the given input, interviewer will be not happy. Also for pointing intersecting node to previous node, cannot be possible as there are two node previous it for two different linked list. This is of no use. case 2: where you are using extra space for creating a copy of reversed linked list. As this uses extra space, this is also not recommended when you can solve the same problem with constant space.

[@cricwhiz151]

nice explaination thank you

[@ytg6663]

Coming to last solution, wont it stuck in loop if no intersection found ???

[@tannukumari5144]

The 2nd optimal approach is 🔥, Get well soon bhaiya..waiting for your next message on telegram just after posting new video :)

[@naro.tam_]

I was able to code 1st optimal by myself but 2nd one was jusssss great

[@nileshsinha7869]

I just solved this question last night. Amazing explanation

[@takeUforward]

Glad it helped!

[@anushak1446]

understood thank you

[@yash30095]

understood!

[@AmarjeetKumar-to9ub]

Thank You :)

[@little-by-little-one-trave1770]

Great explanation. But will the last concise optimal solution run if they do not have intersection ?

[@jayuchawla1892]

no 😫

[@ayanagrawal]

Can anyone please tell how is the case of no intersection handled in the last approach...

[@samstar9777]

well, at the end of second iteration, both of the nodes will be equal to NULL and therefore equal to each other thus eventually terminating the while loop

[@atibhu]

grt explaination, thanks for this...

[@rtm4829]

In the C++ code if there is no intersection point in LL how will a== b (To stops while loop)??

[@khageshbansal2400]

Wouldn't your algo return wrong answer of 1 at 16:11 because head a and head b have same values.

[@niyom8866]

ANSWER COMES RIGHT., BUT I HAVE SAME DOUBHT

[@saurabhahuja6707]

Can we dirty node by adding one more member visitedcount by doing so ,,, we can iterate on first linked list and update visited to 1 then traverse second linked list. And if we found alrrady visited 1 then this is the intersection point ....complexity is o(m+n)

[@democratcobra]

Thanks for uploading vai....u r my motivation.

[@amanaswal11]

Thankyou so much for the Optimal 2 approach 😻🚀

[@subhajeetchakraborty1791]

wow 2nd best approach was similar to hare and tortoise method

[@jeevanreddy9895]

Amazing man 🙏🙏🙏🙏🙏

[@programmertik2046]

first i like your videp then i watch it !!

[@deependu__]

Awesome. Thanks.

[@AB-tp9eg]

Happy new year bhaiya, I have one doubt please answer, In the last you mentioned two optimal sol. of same complexity. Should we answer only last one or both optimal sol. in an interview? And bhaiya i think the complexity of last one optimal sol. is O(N+(M-N)+N) i.e. O(N+M) [in the worst case] where N->is smaller LL & M->is longer LL. Please explain

[@SANCHITJAIN_]

great explanation...loved it :)

[@madhunitesh1567]

Really the 2nd optimal solution is just 🔥🔥🔥.

[@aaryansingh3783]

Is the dummy node as mentioned by bhaiya same as pointer to a Node (head of linked list) like Node * temp = head

[@soummodipsaha5363]

How to find the length of 2 lists simultaneously in Optimal 1 ??

[@pratikvyas3384]

how common node is different from intersection node? like i can see there is '1' common in both the llist, then why we are considering 8 as the intersecting node? can anyone please explain me?

[@jobanpreetsingh2370]

In the problem we are actually finding the intersection point and after that point the both list have same nodes till tail (end) of both lists. 1 is common to both but not a intersection point because after 1 the lists don't have same nodes. While after 8 they have same nodes till the end. 😊😊

[@abdurrahaman388]

Could we able to solve this by reversing both link list and then traverse from back ?

[@abhishekjha5651]

It is mentioned in the question that, you cannot change the original structure of the linked list.

[@priyanshunandan9648]

@@abhishekjha5651 usko v pata hoga, but usko reverse karke karna hoga. Wtw abdur yes we can do it. You just have to call reverse functions two times for list1 and list2 and now you can perform the same operation you will get the same answer. The point of intersection won't change even after reversing.

[@rounakpattanayak6816]

2nd optimal soln is faulty I guess ...if there is no insertion point I think 2nd soln will not work

[@manistrikes]

It will work....if both of them are non intersecting......at one point while traversing...u will be reaching null from both lists..and u will be returning null....make one test case and try...it will work

[@savalalingeshreddy6750]

Thanks for the video bro good explanation Keep doing

[@devbhattacharya153]

Thanks a lot striver

[@mayankraj5690]

Method 2 solution C++ : . . . . ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *tempa = headA,*tempb = headB; int count1=0,count2=0; while(tempa!=NULL){ tempa = tempa->next; count1++; } while(tempb!=NULL){ tempb = tempb->next; count2++; } int n = count2-count1; if(ncount2)?headA:headB; ListNode *temp2 = (count1next; n--; } while(temp1!=NULL){ if(temp1==temp2) return temp1; temp1=temp1->next; temp2=temp2->next; } return NULL; }

[@praharshsingh2095]

How will the third approach work is the abs(length1 - length2) is equal to 1? Ex - 1 2 8 2 2 1 8 9 9 both pointer will move one at a time and will never meet

[@takeUforward]

It will never meet because the test case is wrong. It should have been 1,2,8,2,2 1,8,2,2

[@heyrmi]

Bhaiya I am late. But I am glad I here.

[@AinasDiaries]

the optimal solution solution 1 is printing the the output in gfg....whats the issue??

[@priyanshunandan9648]

May be you've made a mistake in your logic 😌

[@debdhritiroy6868]

beautifully explained

[@nknidhi321]

Brilliant. Thank you

[@MidoValo]

like like your so smart thank you so much

[@ketankhandelwal8626]

bro i just wanna know one thing do u crack all this intutions by yourself or have seen somewhere or it just came by practice? ..

[@definitelyacat]

how on earth do you think out such solutions?

[@AMANSAINI-qq7pm]

how can we do this using stack ?? anyone know ??

[@aryansinha1818]

12:20 Optimized Solution