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 Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s