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

Question

我写了找到两个链表的合并点的代码，但是在大多数测试用例中，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，所以这里return输入了错误的数据。在后面类似的 if 块中也犯了同样的错误。

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

上面的if明明是一个合并点，但是错误的是return0.应该returnnode1.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^th 个节点处具有合并点，而该节点只是第二个列表中的第 3^rd 个。所以 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;
}

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

Find the merge point of two LinkedLists : Run time error

java

runtime-error

linked-list

一个解决方案

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

Find the merge point of two LinkedLists : Run time error

java

runtime-error

linked-list

一个解决方案

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