CODEWITHSUNDEEP
c++data-structuresmergelinked-listnodes
L. Dai
L. Dai

Reputation: 239

segmentation fault while finding merge node?

I'm working on this find merge node method on hackerrank. My approach is: while both of the nodes are not null, I want to move one of the list to their next node, that's what flag variable is for. But somehow it's giving me segmentation fault? Did I accidentally access a null variable? Someone please enlighten me. Below is my method code.

Constraint: Both lists will converge and both lists are non-NULL

int FindMergeNode(Node *headA, Node *headB)
{
    // Complete this function
    // Do not write the main method. 
    bool flag = true;
    while(headA != headB){
        if(flag) headA=headA->next; 
        else headB=headB->next; 
        flag = !flag;
    }   

    return headA->data;  //or headB->data;
}

Upvotes: 0

Views: 68

Answers (2)

Hariom Singh
Hariom Singh

Reputation: 3632

Why to use flag directly use the condition to check if it is the last node 

if(headA->next ==NULL) 
headA=headA->next; 
else if (headB->next== NULL )
headB=headB->next;

Complete solution would be something

int FindMergeNode(Node *headA, Node *headB) {
    Node *currentA = headA;
    Node *currentB = headB;

    //Do till the two nodes are the same
    while(currentA != currentB){
        //If you reached the end of one list start at the beginning of the other one
        //currentA
        if(currentA->next == NULL){
            currentA = headB;
        }else{
            currentA = currentA->next;
        }
        //currentB
        if(currentB->next == NULL){
            currentB = headA;
        }else{
            currentB = currentB->next;
        }
    }
    return currentB->data;
}

Upvotes: 1

Yuval Ben-Arie
Yuval Ben-Arie

Reputation: 1290

You make two assumptions:
1. There exists such node.
2. The distance of this node from the beginning of each list differs by at most 1 between the two lists. You alternately move forward in one list and then check to see if you got to the same node (by address). so if list1 has no nodes before the one you are looking for, and list2 has 2 nodes before it, you won't find a match.

If I understand your question correctly, the truth is that the distance from the end of the list is the same (because their tails are the same).

Upvotes: 3

Related Questions