java查找两个LinkedList的合并点：运行时错误

Question

我已经编写了找到两个LinkedList的合并点的代码，但是在大多数测试案例中，hackerrank抛出运行时错误，我只是想知道是什么导致了它。下面是我的代码：

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

有几个问题：

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

如果上述条件确实为真，则合并点不是node1，而是node2，因此此处返回错误的数据。在下面类似的if块中也会犯同样的错误

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

上面的if清楚地标识了一个合并点，但是返回0是错误的。它应该返回node1.data

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

上面的代码意味着没有合并点。鉴于挑战承诺存在一个合并点，这种情况永远不会发生

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

上面的while循环假设到合并点的距离在两个列表中是相同的，但不能这样假设。可能第一个列表的合并点位于其第6个^{节点，而该节点只是第二个列表中的第3个节点。因此while循环将通过合并点而没有注意到它}

然后在循环之后，您有：

return node1.data;

但是while循环结束的概率大约为50%，因为node1变成了null。如果发生这种情况，表达式node1.data将触发异常，这就是您看到的情况

作为结论，我们可以说您的算法不足以完成此任务

解决方案

有几种方法可以实现这一点，但一种方法是首先统计第一个列表和第二个列表中的节点数。如果一个比另一个长，那么您已经可以从最长的列表中删除前几个节点，这样您就剩下两个同样长的列表。在的时刻，您的while循环将完成这项工作，这样您就可以确保到合并点的距离在两个列表中是相同的

以下是建议的代码：

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