// method 1
node* find_x(node *head1,node *head2) {
node * L1_aux = head1;
node * L2_aux = head2;
//traverse both lists - O(m+n)
// traverse list 1 and find length1
int l1_length=0;
while(L1_aux != NULL) {
l1_length++;
L1_aux = L1_aux->next;
}
// traverse list 2 and find length2
int l2_length=0;
while(L2_aux != NULL) {
l2_length++;
L2_aux = L2_aux->next;
}
int diff = abs(l1_length - l2_length);
// add this offset to the head pointer
// of the longer list
if(l1_length = max(l1_length,l2_length)) {
L1_aux = head1 + diff;
}else {
L2_aux = head2 + diff;
}
// traverse one more time
// to get the common node
// O(max(m,n)
int found = 0;
while(L1_aux != NULL && L2_aux != NULL) {
if(L1_aux == L2_aux) { // Or L1_aux->data == L2_aux->data
printf("found = %d\n", L1_aux->data);
found = 1;
break;
}
L1_aux = L1_aux->next;
L2_aux = L2_aux->next;
}
if(found == 1) return L1_aux; // Or, return L2_aux;
else return NULL;
}
// Overall = O(m+n) + O(max(m,n)) = O(m+n)