Gymnastique algorithmique 12

Intersection Point of Two Lists

La description

Les têtes des deux listes liées sont passées, alors découvrez si les deux listes liées se croisent réellement, Implémentons un algorithme qui renvoie cette intersection. Renvoie null s'il n'y a pas d'intersections. Être une intersection signifie que les nœuds ont la même adresse en mémoire.

Dans l'exemple ci-dessous, aucune des listes ne se coupe. Dans l'exemple suivant, il existe un nœud contenant 12 données à l'intersection, de sorte que ce nœud est renvoyé.

Solution1 Tout d'abord, la première méthode d'implémentation qui me vient à l'esprit est de savoir si le nœud de la première liste liée existe également dans la deuxième liste liée. Un algorithme inefficace avec un temps d'exécution de O (m * n) (m et n sont les longueurs de la liste liée). Dans ce cas, le temps d'exécution est lent, mais la complexité de l'espace est O (1) car il analyse uniquement à l'aide de deux pointeurs.

Solution2 Mais disons que vous avez beaucoup de mémoire et que vous souhaitez améliorer votre temps d'exécution plus efficacement. Dans ce cas, la première chose qui me vient à l'esprit est Il s'agit d'utiliser une structure de données qui utilise HashTable. Par conséquent, nous allons l'implémenter en utilisant le HashSet de Java. Tout d'abord, ajoutez des nœuds à HashSet tout en analysant linéairement les éléments d'une liste liée. Après cela, vérifiez si le même nœud existe dans le jeu de hachage lors de l'analyse linéaire de la deuxième liste liée. Puisque l'accès aux éléments de HashSet est bien sûr O (1), le temps d'exécution de cette implémentation est O (m + n), ce qui est plus efficace.

la mise en oeuvre

Intersect.java

class Intersect{
  public LinkedListNode findintersect(LinkedListNode head1,LinkedListNode head2) {

    LinkedListNode cur1 = head1;
    LinkedListNode cur2 = head2;
    LinkedListNode interSectionNode = null;
    HashSet<LinkedListNode> hashSet = new HashSet<>();

    while (cur1 != null) {
      hashSet.add(cur1);
      cur1 = cur1.next;
    }

    while (cur2 != null) {
      if (hashSet.contains(cur2)) {
        interSectionNode = cur2;
        break;
      }
      cur2 = cur2.next;
    }

    return interSectionNode;
  } 
}

Solution3 Supposons maintenant qu'il y ait une énorme quantité de données dans la liste liée et considérons si nous pouvons améliorer un peu plus l'efficacité de la mémoire. Tout d'abord, supposons que les deux listes liées ont la même taille. Dans ce cas, vous pouvez comparer les adresses de nœud en utilisant deux pointeurs différents depuis le début des deux. Si ces adresses correspondent, cela signifie qu'il s'agit d'une intersection. S'ils ne correspondent pas, faites avancer les deux pointeurs ** simultanément ** de un pour comparer les adresses. Répétez ce processus jusqu'à ce que vous trouviez une intersection ou que les deux listes aient disparu. Maintenant, si les longueurs de liste sont différentes, utilisons ce concept pour le problème.

1. Trouvez les longueurs des deux listes liées: L1 et L2. 2.Calculez la différence de longueur entre L1 et L2. ré= | L1-L2 |
2. Déplacez le pointeur de la tête de la différence de "d" par rapport à la liste la plus longue.
3. La longueur de la liste à partir du pointeur déplacé est maintenant la même que la longueur de l'autre liste.
4. Parcourez les deux listes et comparez les nœuds jusqu'à ce que les adresses correspondent ou que la liste atteigne la fin.

Avec cet algorithme, le temps d'exécution reste O (n + m) et l'efficacité de la mémoire peut être O (1).

Exemple

la mise en oeuvre

Intersect.java

class Intersect{
  public LinkedListNode findIntersect(LinkedListNode head1,LinkedListNode head2) {

    LinkedListNode list1node = null;
    int list1length = getLength(head1);
    LinkedListNode list2node = null;
    int list2length = getLength(head2);

    int length_difference = 0;
    if(list1length >= list2length) {
      length_difference = list1length - list2length;
      list1node = head1;
      list2node = head2;
    } else {
      length_difference = list2length - list1length;
      list1node = head2;
      list2node = head1;
    }

    while(length_difference > 0) {
      list1node = list1node.next;
      length_difference--;
    }

    while(list1node != null) {
      if(list1node == list2node) {
        return list1node;
      }

      list1node = list1node.next;
      list2node = list2node.next;
    }
    return null;
  }

  private int getLength(
    LinkedListNode head) {      
    int list_length = 0;
    while(head != null) {
      head = head.next;
      list_length++;
    }
    return list_length;
  }
}