Find merge point of two linked list

  Рет қаралды 108,252

mycodeschool

mycodeschool

Күн бұрын

Пікірлер: 121
@manojpandey7517
@manojpandey7517 4 жыл бұрын
Even if there are oceans of content available online on a same topic, mycodeschool always stands out of them. It's kinda sad why you guys stopped making more videos.
@pulkitsharma7105
@pulkitsharma7105 4 жыл бұрын
The founder of mycodeschool died in an accident 5 years ago
@sheruloves9190
@sheruloves9190 4 жыл бұрын
@@pulkitsharma7105 Fuck.. was that the one delivering dsa topics?
@PrathamGupta2408
@PrathamGupta2408 4 жыл бұрын
RIP
@merohan619
@merohan619 4 жыл бұрын
@@sheruloves9190 yes, he was a national level coder.
@saketkumar5884
@saketkumar5884 3 жыл бұрын
@@sheruloves9190 No
@lukestumpf1524
@lukestumpf1524 5 жыл бұрын
Make sure to set d = -d in the swap section of code so if you need to swap you actually go through all of the values you need. Great video!
@swami2672
@swami2672 3 жыл бұрын
Thanks for the video. Instead of swapping, just traverse the larger linked list in advance. CODE: /** Definition for singly-linked list. class ListNode { public int val; Public ListNode next; ListNode(int x){ val = x; next = null; } } */ public class MergePoint { public int getLength(ListNode a) { int count = 0; ListNode temp = a; while (temp != null) { count++; temp = temp.next; } return count; } //Traverse the larger list by d times //So both the starting points of the list will come on the same track //Starting point of b will be now 40 and not 200 public ListNode traverseD(ListNode a, int d) { for (int i = 0; i < d; i++) a = a.next; return a; } public ListNode getIntersectionNode(ListNode a, ListNode b) { int a_length = getLength(a); int b_length = getLength(b); int d; //Whoever is larger will traverse in extra if (a_length > b_length) { d = a_length - b_length; a = traverseD(a, d); } else { d = b_length - a_length; b = traverseD(b, d); } //Now a and b are on the same track //100 on A and 40 on B while (a != null && b != null) { if (a == b) return a; a = a.next; b = b.next; } //If there are no merging points return null; } }
@arjitaagrawal270
@arjitaagrawal270 3 жыл бұрын
Great explanation..the practical example made it even more interesting and easy to understand. Such examples are appreciated
@subham-raj
@subham-raj 5 жыл бұрын
*If you use HashSet then time-complexity would be O(m + n) and Space-complexity would be either O(n) or O(m) depends on which linked list data you would like to store in the HashSet.*
@subham-raj
@subham-raj 5 жыл бұрын
FOUND ONE MORE COOL SOLUTION: int FindMergeNode(Node headA, Node headB) { Node currentA = headA; Node currentB = headB; //Do till the two nodes are the same while(currentA != currentB){ //If you reached the end of one list start at the beginning of the other one //currentA if(currentA.next == null){ currentA = headB; }else{ currentA = currentA.next; } //currentB if(currentB.next == null){ currentB = headA; }else{ currentB = currentB.next; } } return currentB.data; }
@nikhilnikhil3517
@nikhilnikhil3517 3 жыл бұрын
@@subham-raj how do you ensure that this code runs for the linked lists having no intersection
@harikishanpuvvala5973
@harikishanpuvvala5973 7 жыл бұрын
This video is good. With an exception that it is mistyped as 80 instead of 30 in the list A for the node 140.
@TheKundan11
@TheKundan11 10 жыл бұрын
Nice explanation !!!! And good approach of solving a problem first in brute force and then going on optimizing it .
@flockerlocker
@flockerlocker 10 жыл бұрын
To decide the longer list you are performing a swap , but you can also do without swap using lengths of both lists if (lengthOfB > lengthOfA) //Move B till lengthOfB - lengthOfA; else if (lengthOfB < lengthOfA) //Move A till lengthOfA - lengthOfB;
@subham-raj
@subham-raj 5 жыл бұрын
Bro you have to swap the head pointers as you might traverse the wrong list. Think about it.
@krsingh.shubham
@krsingh.shubham 4 жыл бұрын
mah-god, after moving through so many tutorials for this problem, none explained me with this much clarity.
@ytg6663
@ytg6663 3 жыл бұрын
Ok. Thank me later
@rajasekharkalakangeri1708
@rajasekharkalakangeri1708 6 жыл бұрын
finding length ofeach linked list also takes some time here. Here is my approach 1. Insert all the nodes of linked list A to a simple array (X) 2. Insert all the nodes of linked list B to a simple array (Y) 3. Start a loop to fetch from both the arrays starting from the last element, every time nodes from both arrays will be equal. At an instance nodes from arrays go unmatch, break the loop and return the previous instance as the output.
@rajasekharkalakangeri1708
@rajasekharkalakangeri1708 6 жыл бұрын
if it is a double linked list, we don't require any arrays
@ritikashishodia3829
@ritikashishodia3829 3 жыл бұрын
great explanation i am solved this problem at hacker rank I do not understand what is actually merge point ....hacker rank give mycodeschool channel link ..then finally i understand what is merge point.
@yasser_hussain
@yasser_hussain 6 жыл бұрын
A set implemented as hash has O(1) insert, delete, find time complexity. So even for Hashset solution we will get O(m+n) time albeit space complexity will be O(n).
@codingcart
@codingcart 4 жыл бұрын
kzbin.info/www/bejne/jZSylZaLfbR0Z68
@prabhu2263
@prabhu2263 6 жыл бұрын
What happens in the following cases:- 1. If the common nodes are in the starting of both linked lists? like L1 - 1,2,3,4,5,6,7,8. L2 - 1,2,3,9,10,11,12. 2. If both the lists has same length?. Then we end up again in the equivalent method of brute force.
@pymondo1147
@pymondo1147 6 жыл бұрын
1. It seems in singy linked list we can never have node pointing two address . So this is invalid. It will be unique memory for both the lists.
@divyamsh2115
@divyamsh2115 5 жыл бұрын
if the first node itself is matching then return the first node,else follow this approach!
@Shree__98
@Shree__98 4 жыл бұрын
Sooo well explained..🎉 You deserve appreciation 👏
@CSshreyas
@CSshreyas 8 жыл бұрын
what if the liked lists are modified in way that they have some diverging point after they merge? and the lists are of different length? something like two trains have just few common stations Train 1 stops at station A -> B -> C -> D -> E -> F. Train 2 stops at station H -> I -> C -> D -> J -> K -> L -> M
@zoltanie
@zoltanie 7 жыл бұрын
then it's not a linked list!
@ChandraShekhar-by3cd
@ChandraShekhar-by3cd 4 жыл бұрын
Your explanation was Perfect!..Please upload more videos
@codingcart
@codingcart 4 жыл бұрын
kzbin.info/www/bejne/jZSylZaLfbR0Z68
@rishabsharma5307
@rishabsharma5307 4 жыл бұрын
he died
@jaysahu357
@jaysahu357 6 жыл бұрын
very very nice you teach me many thing in one video about how to optimize the code,thank a lot
@sidddcloud
@sidddcloud 5 жыл бұрын
Also you can join the tail of both list. Then find the starting point of loop
@prateektewary7526
@prateektewary7526 3 жыл бұрын
For that you will require a doubly linked list to traverse back from tail.
@FitnessChaos
@FitnessChaos 3 жыл бұрын
Good explanation but the optimal solution is not dynamic. You actually don’t know which of the A or B nodes is bigger so you have to check and iterate for that too
@avnishgupta8731
@avnishgupta8731 9 жыл бұрын
sir in this there is error at 4:40 in the link list A the 2 nd node which has data value 6 has the value in the next pointer 30 and not 80. plz correct it
@jamesward2946
@jamesward2946 6 жыл бұрын
This is a great tutorial. Thanks for the corner cases explanation at the end :).
@codingcart
@codingcart 4 жыл бұрын
kzbin.info/www/bejne/jZSylZaLfbR0Z68
@thinhnguyenvan7003
@thinhnguyenvan7003 3 жыл бұрын
I think in method 2, we use dictionary will give you linear time complex
@chitrasomasingh5388
@chitrasomasingh5388 10 жыл бұрын
i didnt understand the condition: if(addresses.find(A)!=addresses.end()) what is the use of addresses.end overhere ??
@mycodeschool
@mycodeschool 10 жыл бұрын
Chitrasoma Singh There is this concept of iterators in standard template library of C++.. Go through this - community.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary
@s20_d84
@s20_d84 10 жыл бұрын
Nice explanation with real tym example .. I liked this tutorial ... keep it up :)
@sriramiyer9840
@sriramiyer9840 4 жыл бұрын
in the last approach, d should be set equal to abs(n-m), i.e., d = abs(n-m); as the value of n-m can be negative too
@naveendara8646
@naveendara8646 4 жыл бұрын
Check the if statements It has a d=m-n statement
@kaustavbora2024
@kaustavbora2024 4 жыл бұрын
Swap function is wrong Please update it Right One:- if(m > n) { SinglyLinkedListNode* temp; temp=head1; head1=head2; head2=temp; d=m-n; }
@suguruchhaya3194
@suguruchhaya3194 3 жыл бұрын
Your video was so damn easy to understand. RIP and thank you.
@blasttrash
@blasttrash 6 жыл бұрын
Is this Harsha? May his soul rest in peace. :'(
@subham-raj
@subham-raj 5 жыл бұрын
What happened to him?
@yashpreetbathla4653
@yashpreetbathla4653 5 жыл бұрын
@@subham-raj He passed away in accident :"(
@vikranttyagiRN
@vikranttyagiRN 4 жыл бұрын
RIP
@anolhshete
@anolhshete 8 жыл бұрын
In the last solution the time complexity will be O(max(m,n)) ? Is it correct or O(m+n) is correct , I know we can remove the constant factor but which is logically correct.
@sidddcloud
@sidddcloud 5 жыл бұрын
I think o(m+n) means whichever is greater. So they are basically same.
@ravindercool005
@ravindercool005 9 жыл бұрын
Very nice explanation ..Thnks alot sir .
@magicsmoke0
@magicsmoke0 9 жыл бұрын
How would you do the Set approach in C# where references to managed objects don't have addresses (you would have to do some trickery with the GCHandle to get it)?
@jsrgbh0
@jsrgbh0 8 жыл бұрын
Have seen few of your videos and liked them all. Most of your solutions are focused on C and C++, Possible for you to provide the Java code snippet as well?
@ShekharKumar8034
@ShekharKumar8034 10 жыл бұрын
Nice and simple explanation sir.. Thanks :)
@zy5522
@zy5522 9 ай бұрын
Thanks😊
@vijayendrasdm
@vijayendrasdm 10 жыл бұрын
For the approach 2, why did not you use unordered_map ? unordered_map has insertion/retrieve complexity of O(1). By using this we could have reduced TC to O(n) . Correct me if I am wrong
@lorenzocastillo6850
@lorenzocastillo6850 10 жыл бұрын
O(M+N) time, but obv you need space for the hash table.
@udaykiran-yi2dv
@udaykiran-yi2dv 8 жыл бұрын
excellent Explanation
@liwaiyip1769
@liwaiyip1769 4 жыл бұрын
Amazing job! Thank you very much.
@TheAbhijeetidiot
@TheAbhijeetidiot 10 жыл бұрын
please upload some lectures on conditional statements and loops, arrays, functions and storage classes.
@seemcat
@seemcat 5 жыл бұрын
Great explanation. Thanks!
@AddieInGermany
@AddieInGermany 7 жыл бұрын
Nicely explained. Thanks
@suguruchhaya3194
@suguruchhaya3194 3 жыл бұрын
Who else is comming from the HackerRank question? Just want to let you know that you have to return the '.data' of the node instead of the node itself in the question.
@nikhilnikhil3517
@nikhilnikhil3517 3 жыл бұрын
Shouldn't the time complexity be O(max(m,n)) as we are basically traversing the longer list fully in worst case i.e. when no merge point is found.
@abhishekkaukuntla6762
@abhishekkaukuntla6762 8 жыл бұрын
What if the first node itself is the merge point? What's the rule to evaluate d then, considering length(A) < length(B)? If we skip d places, we would miss the merge point.
@Gre05
@Gre05 8 жыл бұрын
+Nikolay Jivkov I didn't understand it, because if the first node is merge with first node of B, we can skip it.
@mithessen
@mithessen 8 жыл бұрын
It seems that there is an implicit assumption that after the merge point the lists remain same throughout. If there were multiple merge points to be considered such as in lists which converged, diverged and then re-converged, then it would need additional checks and balances.
@preetsinghkhalsa1204
@preetsinghkhalsa1204 6 жыл бұрын
A list cannot diverge since there's only one parameter for next node in the structure.
@yasser_hussain
@yasser_hussain 6 жыл бұрын
That can only happen if both lists are identical. Remember linked lists can't diverge.
@NiranjhanaNarayanan
@NiranjhanaNarayanan 8 жыл бұрын
Hey when we are passing the head node pointer (for the length function), isn't that by reference? So when we traverse it, doesn't the value get modified and the value of the start of the linked list get lost?
@NiranjhanaNarayanan
@NiranjhanaNarayanan 7 жыл бұрын
Yeah, got that, thanks!
@aayush5474
@aayush5474 5 жыл бұрын
waht will main look like?
@Niteshkumar-zd3kr
@Niteshkumar-zd3kr 5 жыл бұрын
Are you comparing addresses or the values?
@subham-raj
@subham-raj 5 жыл бұрын
The node as a whole.
@codingcart
@codingcart 4 жыл бұрын
kzbin.info/www/bejne/jZSylZaLfbR0Z68
@anupamshankardey8737
@anupamshankardey8737 7 жыл бұрын
which IDE have you used during this lesson?
@chiranjeevthomas4796
@chiranjeevthomas4796 6 жыл бұрын
it's codeblocks
@bantykumar5734
@bantykumar5734 6 жыл бұрын
Notepad++
@KhaledChikhComptable
@KhaledChikhComptable 10 жыл бұрын
Good tutorial
@siddharth__pandey
@siddharth__pandey 6 жыл бұрын
your website is showing a bad gateway error.. please fix
@mayanksrivastava4452
@mayanksrivastava4452 7 жыл бұрын
amazing video
@AbhayKumar-uw8or
@AbhayKumar-uw8or 4 жыл бұрын
i think its wrong as what if the d more nodes itself contain the merge point that you have just skipped to make the length same
@redraushan
@redraushan 4 жыл бұрын
I was banging my forehead for hours thinking how could two separate linked list can have a merge point, thank god I finally am here.
@sureshdharavath1191
@sureshdharavath1191 10 жыл бұрын
In brute force without finding the length lists can't it possible ? I guess by creating two temporary nodes which points to the head of the given nodes.
@mycodeschool
@mycodeschool 10 жыл бұрын
Suresh D.Naik Can you detail your approach?
@saurabhchauhan1567
@saurabhchauhan1567 8 жыл бұрын
+Suresh Dharavath it is possible but i will not change the complexity of the solution
@sartmeh1
@sartmeh1 8 жыл бұрын
He means by using two while loops with each while loop designated with either list to check for NULL in link lists.This can save up a little bit of memory but still the complexity shall remain same i.e. O(mn).
@CSshreyas
@CSshreyas 8 жыл бұрын
what about going to the end of the list and traverse back until there the nodes have same value?
@codingcart
@codingcart 4 жыл бұрын
kzbin.info/www/bejne/jZSylZaLfbR0Z68
@curiosity9861
@curiosity9861 4 жыл бұрын
At 1:29 we have different addresses of value 7 in linked list 1 and linked list 2 so how we can check for the equality of it?
@prateektewary7526
@prateektewary7526 3 жыл бұрын
Here we are not searching for similar values of nodes rather a "merge point". The two linked list at 1:29 have same values of two nodes but no merge point.
@hassnainali6872
@hassnainali6872 5 жыл бұрын
Can't we recursively go to the end of each list, and on each return, compare the pointers with each other up till the last point where they are similar ?
@redraushan
@redraushan 4 жыл бұрын
That would still be brute-force way way of doing it, basically you are asking why to do merge sort if be can do bubble sort, I think that's the difference.
@parmeetsingh7410
@parmeetsingh7410 6 жыл бұрын
can we compare node's data instead of node's address???
@utsavdahiya3729
@utsavdahiya3729 6 жыл бұрын
No, data values are not unique to each node
@parmeetsingh7410
@parmeetsingh7410 6 жыл бұрын
utsav dahiya can you please explain through an example,I am still confused?
@mavrck159
@mavrck159 6 жыл бұрын
SnackDown is here! Only one global champion will take the title home. Let the Code War begin! Registrations are now OPEN for SnackDown 2019! www.codechef.com/snackdown?ref=sssshhhh
@shruthib6635
@shruthib6635 6 жыл бұрын
what if 2 lists diverge after some point.... How are we handling this case
@shankarn4021
@shankarn4021 6 жыл бұрын
The linked list(mentioned in the video) has only one next* pointer, so it's impossible to have the list point to 2 different nodes.
@RajbirYadav
@RajbirYadav 9 жыл бұрын
awesome!
@FrozenByTheSun
@FrozenByTheSun 6 жыл бұрын
Is this Harsha?
@blasttrash
@blasttrash 6 жыл бұрын
I had the same question. If it was, I just feel so sad. May his soul rest in peace.
@urcristiano77882
@urcristiano77882 6 жыл бұрын
who is harsha ?
@blasttrash
@blasttrash 6 жыл бұрын
Harsha is one of the two guys who started this channel. Apparently Harsha met with accident or something.
@urcristiano77882
@urcristiano77882 6 жыл бұрын
okayy thanks
@mybozlo
@mybozlo 9 жыл бұрын
In #3 case, what if the merge point in d area ?
@SourabhVartak1985
@SourabhVartak1985 9 жыл бұрын
+IL JUN LEE The d area is where one linked list has more elements than the other linked list. So, the merge point can not occur in the d area because only one list is active there.
@arpitsatnalika
@arpitsatnalika 4 жыл бұрын
This code will fail for linked list like this [4,1,8,4,5] and [5,6,1,8,4,5]
@kunalsoni7681
@kunalsoni7681 4 жыл бұрын
😍😍😍😊😊😊😊
@lyfokzz3848
@lyfokzz3848 4 жыл бұрын
unfortunatly he passed away bro...
@kunalsoni7681
@kunalsoni7681 4 жыл бұрын
@@lyfokzz3848 what it mean bro
@lyfokzz3848
@lyfokzz3848 4 жыл бұрын
The instructors name was Late Harsha suryanarayan. He was the best coder of all time.You can google it for more information.
@kunalsoni7681
@kunalsoni7681 4 жыл бұрын
@@lyfokzz3848 thanks bro😉
@lyfokzz3848
@lyfokzz3848 4 жыл бұрын
@@kunalsoni7681 welcm dude. And happy coding.
Reverse a linked list using recursion
8:55
mycodeschool
Рет қаралды 610 М.
you will never ask about pointers again after watching this video
8:03
The IMPOSSIBLE Puzzle..
00:55
Stokes Twins
Рет қаралды 85 МЛН
1, 2, 3, 4, 5, 6, 7, 8, 9 🙈⚽️
00:46
Celine Dept
Рет қаралды 83 МЛН
ЗНАЛИ? ТОЛЬКО ОАЭ 🤫
00:13
Сам себе сушист
Рет қаралды 4,2 МЛН
Trick-or-Treating in a Rush. Part 2
00:37
Daniel LaBelle
Рет қаралды 43 МЛН
Learn Linked Lists in 13 minutes 🔗
13:24
Bro Code
Рет қаралды 336 М.
Object-Oriented Programming is Embarrassing: 4 Short Examples
28:03
Brian Will
Рет қаралды 2,1 МЛН
5 Signs of an Inexperienced Self-Taught Developer (and how to fix)
8:40
Reverse a linked list - Iterative method
13:50
mycodeschool
Рет қаралды 778 М.
L12. Find the intersection point of Y LinkedList
32:05
take U forward
Рет қаралды 78 М.
Reverse a string or linked list using stack.
16:25
mycodeschool
Рет қаралды 386 М.
The IMPOSSIBLE Puzzle..
00:55
Stokes Twins
Рет қаралды 85 МЛН