Find merge point of two linked list

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:

See series on linked list here:

See series on time complexity here:

About sets:

You may also like/follow us on Facebook/Twitter:

[manojpandey]

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.

[lukestumpf]

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!

[swami]

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;
}
}

[arjitaagrawal]

Great explanation..the practical example made it even more interesting and easy to understand. Such examples are appreciated

[harikishanpuvvala]

This video is good. With an exception that it is mistyped as 80 instead of 30 in the list A for the node 140.

[TheKundan]

Nice explanation !!!! And good approach of solving a problem first in brute force and then going on optimizing it .

[krsingh.shubham]

mah-god, after moving through so many tutorials for this problem, none explained me with this much clarity.

[ritikashishodia]

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.

[subham-raj]

*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.*

[flockerlocker]

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;

[rajasekharkalakangeri]

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.

[Shree__]

Sooo well explained..🎉 You deserve appreciation 👏

[jamesward]

This is a great tutorial. Thanks for the corner cases explanation at the end :).

[ChandraShekhar-bycd]

Your explanation was Perfect!..Please upload more videos

[jaysahu]

very very nice you teach me many thing in one video about how to optimize the code, thank a lot

[yasser_hussain]

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).

[s_d]

Nice explanation with real tym example .. I liked this tutorial ... keep it up :)

[prabhu]

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.

[blasttrash]

Is this Harsha? May his soul rest in peace. :'(

[sidddcloud]

Also you can join the tail of both list. Then find the starting point of loop