Find the merge point of two LinkedLists : Run time error

Question

I have wrote the code which finds the merge point of two linkedLists, But in most test cases hackerrank throws run time error, I just wanted to know what causes it. Here is my code below:

static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
  SinglyLinkedListNode node1 =  head1;
  SinglyLinkedListNode node2 = head2;
  if(node1.next == node2){
    return node1.data;
    
  }
  else if(node2.next==node1){
    return node2.data;
    
  }
  if(node1 ==node2){
    return 0;
    
  }
  if(node1 ==null || node2==null){
    return 0;
    
  }
  while(node1 !=null && node2 !=null){
    node1=node1.next;
     node2=node2.next;  
     if(node1==node2){
         break;
       }
     }
     return node1.data;
}

Answer 1

There are several issues:

if(node1.next == node2){
  return node1.data;
}

If indeed the above condition is true, then the merge point is not node1, but node2, so the wrong data is returned here. The same mistake is made in the similar if block that follows.

if(node1 ==node2){
  return 0;
}

The above if clearly identifies a merge point, but it is wrong to return 0. It should return node1.data.

if(node1 ==null || node2==null){
  return 0;
}

The above code would mean there was no merge point. Given that the challenge promises that there is a merge point, this case will never happen.

while(node1 !=null && node2 !=null){
  node1=node1.next;
  node2=node2.next;  
  if(node1==node2){
    break;
  }
}

The above while loop assumes that the distance to the merge point is the same in both lists, but you cannot assume this. It might be that the first list has the merge point at its 6^th node, while that node is only the 3^rd in the second list. So the while loop will pass over the merge point without noticing it.

Then after the loop you have:

return node1.data;

But there is like 50% probability that the while loop ended because node1 became null. And if that happens the expression node1.data will trigger an exception, which is what you saw happening.

As a conclusion we can say that your algorithm is not good enough for this task.

A solution

There are several ways to approach this, but one way is to first count the number of nodes in the first list and in the second list. If one is longer than the other, then you can already dismiss the first few nodes from the longest list so that you are left with two lists that are just as long. At that moment your while loop would do the job, as then you can be sure the distance to the merge point is the same in both lists.

Here is the suggested code for that:

// Helper function to count the number of nodes in a given list:
static int size(SinglyLinkedListNode head) {
    int size = 0;
    while (head != null) {
        head = head.next;
        size++;
    }
    return size;
}

static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
    // Get the difference in list's sizes
    int sizeDiff = size(head1) - size(head2);
    // Dismiss the first node(s) from the longest list until they have an equal size:
    while (sizeDiff < 0) {
        head2 = head2.next;
        sizeDiff++;
    }
    while (sizeDiff > 0) {
        head1 = head1.next;
        sizeDiff--;
    }
    // compare the remaining nodes in tandem.
    while (head1 != head2) {
        head1 = head1.next;
        head2 = head2.next;
    }
    return head1.data;
}