L. Dai L. Dai - 3 years ago 109
C++ Question

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;
}

Answer Source

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).

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download