Find merge point of two linked list
ฝัง
- เผยแพร่เมื่อ 26 ส.ค. 2024
- In this lesson, we have solved a famous programming interview question - finding merge point of two linked list. We have written a C++ implementation.
See source code here:
gist.github.co...
See series on linked list here:
• Introduction to linked...
See series on time complexity here:
• Time complexity of a c...
About sets:
www.cplusplus.c...
You may also like/follow us on Facebook/Twitter:
/ mycodeschool
/ mycodeschool
![[TH] VALORANT Champions Seoul - Grand Final - EDG vs TH](http://i.ytimg.com/vi/WvObMc9VelI/mqdefault.jpg)
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.
The founder of mycodeschool died in an accident 5 years ago
@@pulkitsharma7105 Fuck.. was that the one delivering dsa topics?
RIP
@@sheruloves9190 yes, he was a national level coder.
@@sheruloves9190 No
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!
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;
}
}
mah-god, after moving through so many tutorials for this problem, none explained me with this much clarity.
Ok. Thank me later
Great explanation..the practical example made it even more interesting and easy to understand. Such examples are appreciated
This video is good. With an exception that it is mistyped as 80 instead of 30 in the list A for the node 140.
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.
*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.*
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;
}
@@subham-raj how do you ensure that this code runs for the linked lists having no intersection
Nice explanation !!!! And good approach of solving a problem first in brute force and then going on optimizing it .
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;
Bro you have to swap the head pointers as you might traverse the wrong list. Think about it.
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
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.
if it is a double linked list, we don't require any arrays
i didnt understand the condition:
if(addresses.find(A)!=addresses.end())
what is the use of addresses.end overhere ??
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
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).
th-cam.com/video/WcOdcUHOA1M/w-d-xo.html
This is a great tutorial. Thanks for the corner cases explanation at the end :).
th-cam.com/video/WcOdcUHOA1M/w-d-xo.html
Sooo well explained..🎉 You deserve appreciation 👏
very very nice you teach me many thing in one video about how to optimize the code,thank a lot
Nice explanation with real tym example .. I liked this tutorial ... keep it up :)
Your video was so damn easy to understand. RIP and thank you.
Your explanation was Perfect!..Please upload more videos
th-cam.com/video/WcOdcUHOA1M/w-d-xo.html
he died
Also you can join the tail of both list. Then find the starting point of loop
For that you will require a doubly linked list to traverse back from tail.
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
Check the if statements
It has a d=m-n statement
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
then it's not a linked list!
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.
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.
if the first node itself is matching then return the first node,else follow this approach!
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.
please upload some lectures on conditional statements and loops, arrays, functions and storage classes.
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
Is this Harsha? May his soul rest in peace. :'(
What happened to him?
@@subham-raj He passed away in accident :"(
RIP
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.
I think o(m+n) means whichever is greater. So they are basically same.
I think in method 2, we use dictionary will give you linear time complex
Very nice explanation ..Thnks alot sir .
Amazing job! Thank you very much.
Swap function is wrong
Please update it
Right One:-
if(m > n)
{
SinglyLinkedListNode* temp;
temp=head1;
head1=head2;
head2=temp;
d=m-n;
}
Nice and simple explanation sir.. Thanks :)
Thanks😊
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?
Great explanation. Thanks!
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)?
Nicely explained. Thanks
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.
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
O(M+N) time, but obv you need space for the hash table.
excellent Explanation
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.
+Nikolay Jivkov I didn't understand it, because if the first node is merge with first node of B, we can skip it.
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.
A list cannot diverge since there's only one parameter for next node in the structure.
That can only happen if both lists are identical. Remember linked lists can't diverge.
waht will main look like?
your website is showing a bad gateway error.. please fix
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?
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.
Good tutorial
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?
Yeah, got that, thanks!
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 ?
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.
what about going to the end of the list and traverse back until there the nodes have same value?
th-cam.com/video/WcOdcUHOA1M/w-d-xo.html
amazing video
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
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.
Suresh D.Naik Can you detail your approach?
+Suresh Dharavath it is possible but i will not change the complexity of the solution
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).
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
In #3 case, what if the merge point in d area ?
+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.
what if 2 lists diverge after some point.... How are we handling this case
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.
awesome!
can we compare node's data instead of node's address???
No, data values are not unique to each node
utsav dahiya can you please explain through an example,I am still confused?
Are you comparing addresses or the values?
The node as a whole.
th-cam.com/video/WcOdcUHOA1M/w-d-xo.html
which IDE have you used during this lesson?
it's codeblocks
Notepad++
Is this Harsha?
I had the same question. If it was, I just feel so sad. May his soul rest in peace.
who is harsha ?
Harsha is one of the two guys who started this channel. Apparently Harsha met with accident or something.
okayy thanks
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.
😍😍😍😊😊😊😊
unfortunatly he passed away bro...
@@lyfokzz3848 what it mean bro
The instructors name was Late Harsha suryanarayan. He was the best coder of all time.You can google it for more information.
@@lyfokzz3848 thanks bro😉
@@kunalsoni7681 welcm dude. And happy coding.
This code will fail for linked list like this [4,1,8,4,5]
and [5,6,1,8,4,5]