时间戳

首页 > 解决方案 > 查找两个 LinkedLists 的合并点：运行时错误

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

问题描述

我已经编写了找到两个链接列表的合并点的代码，但是在大多数测试用例中，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;
}

标签： javalinked-listruntime-error

解决方案

有几个问题：

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

推荐阅读