Find Merge (Intersection) Point of Two Linked Lists

Technology CommunityCategory: Linked ListsFind Merge (Intersection) Point of Two Linked Lists
VietMX Staff asked 3 years ago
Problem

Say, there are two lists of different lengths, merging at a point; how do we know where the merging point is?

Conditions:

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

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