closed by
614 views

1 Answer

Best answer
3 votes
3 votes
// 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)
selected by

Related questions

1 votes
1 votes
1 answer
3
Pradip Nichite asked Jan 22, 2016
695 views
Here, what will be the Head->Next , I am confused is it first element 50 or second element 29.
0 votes
0 votes
2 answers
4
Sandeep Singh asked Dec 27, 2015
583 views
Delete the duplicate nodeDelete the alternate duplicate nodeDelete the adjacent nodeNone of these