java查找两个LinkedList的合并点:运行时错误
我已经编写了找到两个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;
}
# 1 楼答案
有几个问题:
如果上述条件确实为真,则合并点不是
node1
,而是node2
,因此此处返回错误的数据。在下面类似的if
块中也会犯同样的错误上面的
if
清楚地标识了一个合并点,但是返回0是错误的。它应该返回node1.data
上面的代码意味着没有合并点。鉴于挑战承诺存在一个合并点,这种情况永远不会发生
上面的
while
循环假设到合并点的距离在两个列表中是相同的,但不能这样假设。可能第一个列表的合并点位于其第6个节点,而该节点只是第二个列表中的第3个节点。因此while
循环将通过合并点而没有注意到它然后在循环之后,您有:
但是
while
循环结束的概率大约为50%,因为node1
变成了null
。如果发生这种情况,表达式node1.data
将触发异常,这就是您看到的情况作为结论,我们可以说您的算法不足以完成此任务
解决方案
有几种方法可以实现这一点,但一种方法是首先统计第一个列表和第二个列表中的节点数。如果一个比另一个长,那么您已经可以从最长的列表中删除前几个节点,这样您就剩下两个同样长的列表。在的时刻,您的
while
循环将完成这项工作,这样您就可以确保到合并点的距离在两个列表中是相同的以下是建议的代码: