Блог

Я написал код, который находит точку слияния двух связанных списков, но в большинстве тестовых случаев 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 amp;amp; node2 !=null){
    node1=node1.next;
     node2=node2.next;  
     if(node1==node2){
         break;
       }
     }
     return node1.data;
}
 

Есть несколько проблем:

 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 amp;amp; node2 !=null){
  node1=node1.next;
  node2=node2.next;  
  if(node1==node2){
    break;
  }
}
 

Приведенный выше while цикл предполагает, что расстояние до точки слияния одинаково в обоих списках, но вы не можете этого предположить. Возможно, в первом списке точка слияния находится на 6-^м узле, в то время как этот узел является только 3-^м во втором списке. Таким while образом, цикл пройдет над точкой слияния, не заметив этого.

Затем после цикла у вас есть:

 return node1.data;
 

Но есть примерно 50% вероятности, что while цикл закончился, потому 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;
}