Find Merge Point of Two Lists

Given pointers to the head nodes of  2 linked lists that merge together at some point, find the Node where the two lists merge. It is guaranteed that the two head Nodes will be different, and neither will be NULL.

In the diagram below, the two lists converge at Node x:

[List #1] a--->b--->c
                     \
                      x--->y--->z--->NULL
                     /
     [List #2] p--->q

Sample Input

The diagrams below are graphical representations of the lists that input Nodes headA and headB and  are connected to. Recall that this is a method-only challenge; the method only has initial visibility to those 2  Nodes and must explore the rest of the Nodes using some algorithm of your own design.

Test Case 0

 1
  \
   2--->3--->NULL
  /
 1

Test Case 1

1--->2
      \
       3--->Null
      /
     1

Sample Output

2
3

Explanation

Test Case 0: As demonstrated in the diagram above, the merge Node’s data field contains the integer .
Test Case 1: As demonstrated in the diagram above, the merge Node’s data field contains the integer .

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

Leave a Comment

Your email address will not be published. Required fields are marked *