ADDITIONAL KNOWLEDGE

Find Merge Point of Two Lists [hackerRank Solution]

2–3 minutes

read

Find Merge Point of Two Lists [hackerRank Solution]

Question:

Given pointers to the head nodes of  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,  and , 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  and  are connected to. Recall that this is a method-only challenge; the method only has initial visibility to those  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  (so our method should return ).
Test Case 1: As demonstrated in the diagram above, the merge Node’s data field contains the integer  (so our method should return ).

 

SOLUTION:

METHOD 1:

int getcount( Node* headA)
{
 int count =0;
 Node *temp = headA;
 while(temp)
 {
 count++;
 temp = temp->next; 
 }
 return count;
 
}
int _FindMergeNode(int d, Node* headA, Node* headB)
{
 Node *cur1 = headA;
 Node *cur2 = headB;
 
 for(int i=0;i<d;i++)
 {
 if(cur1 == NULL)
 {
 return -1;
 }
 cur1 = cur1->next;
 }
 while(cur1 && cur2)
 {
 
 if(cur1->data == cur2 ->data)
 {
 return cur1-> data;
 }
 cur1 = cur1->next;
 cur2 = cur2->next;
 }
 
 return -1;
}

int FindMergeNode(Node* headA, Node* headB) {
 
 int p = getcount(headA);
 int q = getcount(headB);
 int d;
 if(p>q)
 {
 d = p-q;
 return _FindMergeNode(d, headA,headB);
 }
 else
 {
 d = q-p;
 return _FindMergeNode(d, headB,headA);
 }
}

METHOD 2:

int FindMergeNode(Node* headA, Node* headB) {
 // Complete this function
 // Do not write the main method. 
 
 Node *temp1;
 while(headA != NULL)
 {
 temp1=headB;
 while(temp1!=NULL)
 {
 if(headA == temp1)
 {
 return temp1->data;
 }
 temp1=temp1->next;
 }
 
 headA=headA->next;
 }
 return headA->data;
}

// BOTH THE METHODS PASS ALL TEST CASES.

, ,
, , ,

Leave a comment