Say, there are two lists of different lengths, merging at a point; how do we know where the merging point is?
Conditions:
- We don’t know the length
This arguably violates the “parse each list only once” condition, but implement the tortoise and hare algorithm (used to find the merge point and cycle length of a cyclic list) so you start at List 1, and when you reach the NULL at the end you pretend it’s a pointer to the beginning of List 2, thus creating the appearance of a cyclic list. The algorithm will then tell you exactly how far down List 1 the merge is.
Algorithm steps:
- Make an interating pointer like this:
- it goes forward every time till the end, and then
- jumps to the beginning of the opposite list, and so on.
- Create two of these, pointing to two heads.
- Advance each of the pointers by 1 every time, until they meet in intersection point (
IP
). This will happen after either one or two passes.
To understand it count the number of nodes traveled from head1-> tail1 -> head2 -> intersection point
and head2 -> tail2-> head1 -> intersection point
. Both will be equal (Draw diff types of linked lists to verify this). Reason is both pointers have to travel same distances head1-> IP + head2->IP
before reaching IP
again. So by the time it reaches IP
, both pointers will be equal and we have the merging point.
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;
}