Created
May 8, 2016 18:39
-
-
Save jianminchen/2ab387360a0ff2ef41c10c67219fd1c1 to your computer and use it in GitHub Desktop.
HackerRank - Find merge point
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Find merge point of two linked lists | |
Node is defined as | |
struct Node | |
{ | |
int data; | |
Node* next; | |
} | |
*/ | |
int length(Node* head) | |
{ | |
if(head==NULL) | |
return 0; | |
else return length(head->next)+1; | |
} | |
Node* position(Node* head, int pos) | |
{ | |
if(pos==0) | |
return head; | |
else return position(head->next, pos-1); | |
} | |
int common(Node* headA, Node* headB) | |
{ | |
if(headA==headB) | |
return headA->data; | |
else return common(headA->next, headB->next); | |
} | |
int FindMergeNode(Node *headA, Node *headB) | |
{ | |
// Complete this function | |
// Do not write the main method. | |
int l1=length(headA); | |
int l2=length(headB); | |
Node* temp1; | |
Node* temp2; | |
if(l1==l2) | |
temp1=headA, temp2=headB; | |
else if(l1>l2) | |
temp1=position(headA, l1-l2), temp2=headB; | |
else | |
temp1=headA, temp2=position(headB, l2-l1); | |
return common(temp1, temp2); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment