Find Merge Point of Two Lists

PROBLEM :
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

Complete the int FindMergeNode(Node* headA, Node* headB) method so that it finds and returns the data value of the Node where the two lists merge.

Input Format

The FindMergeNode(Node*,Node*) method has two parameters, headA  and headB, which are the non-null head Nodes of two separate linked lists that are guaranteed to converge.
Do not read any input from stdin/console.

Output Format

Each Node has a data field containing an integer; return the integer data for the Node where the two lists converge.
Do not write any output to stdout/console.

Sample Input

The diagrams below are graphical representations of the lists that input Nodes headA and headB 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 2 (so our method should return 2).
Test Case 1: As demonstrated in the diagram above, the merge Node's data field contains the integer 3 (so our method should return 3).

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

/*
   Find merge point of two linked lists
   Node is defined as
   struct Node
   {
       int data;
       Node* next;
   }
*/
int height(Node *) ;
int FindMergeNode(Node *headA, Node *headB)
{
    int h1,h2,no,i ;
    Node *temp,*ptr ;
    h1=height(headA) ;
    h2=height(headB) ;
 
    no=abs(h1-h2) ;
    if(h1>h2)
        {
        temp=headA ;
        i=0 ;
        while(i!=no)
            {
            temp=temp->next ;
            i++ ;
        }
        ptr=headB ;
     
        while(1)
            {
            if(temp==ptr)
                return(temp->data) ;
            temp=temp->next ;
            ptr=ptr->next ;
        }
    }
      else
          {
          temp=headB ;
        i=0 ;
        while(i!=no)
            {
            temp=temp->next ;
            i++ ;
        }
        ptr=headA ;
     
        while(1)
            {
            if(temp==ptr)
                return(temp->data) ;
            temp=temp->next ;
            ptr=ptr->next ;
      }
    }
}

int height(Node *head)
    {
    if(head==NULL)
        return 0 ;
    int c=0 ;
    Node *temp=head ;
    while(temp!=NULL)
        {
        temp=temp->next ;
        c++ ;
    }
    return c ;
}


---------------------------------------------------------------------------------

Comments

Popular posts from this blog

Count ways to N'th Stair(Order does not matter)

Replace all ‘0’ with ‘5’ in an input Integer

Chocolate Distribution Problem

Remove characters from the first string which are present in the second string

Primality Test ( CodeChef Problem code: PRB01 )