Exercice : Listes triées

De la même manière que pour les tableaux, certaines opérations sur les listes chaînées triées peuvent être réalisées de manière plus rapide.

1. Définissez une fonction qui renvoie la plus petite valeur commune à deux listes triées données en paramètres. Par exemple, si les deux listes suivantes sont données : \((1, 3, 4, 7, 9)\) et \((2, 4, 5, 6, 8, 9)\), la fonction devra renvoyer la valeur \(4\). S’il n’y a aucune valeur comune, la fonction renverra -1.

   BEGIN SOLUTION

   int commune(liste *l1, liste *l2) {
       elem *e1 = l1->tete;
       elem *e2 = l2->tete;
       while (e1 != NULL && e2 != NULL) {
           if (e1->valeur == e2->valeur)
               return e1->valeur;
           if (e1->valeur <  e2->valeur)
               e1 = e1->next;
           else
               e2 = e2->next;
       }
       return -1;
   }
   

   END SOLUTION

2. Définissez une fonction qui compte le nombre de valeurs communes stockées dans deux listes chaînées. Par exemple, si les deux listes suivantes sont données : \((1, 3, 4, 7, 9)\) et \((2, 4, 5, 6, 8, 9)\), la fonction devra renvoyer la valeur \(2\).

   BEGIN SOLUTION

   Cette fonction s’obtient simplement à partir de la précédente en continuant de parcourir les listes sans s’arrêter dès la première valeur commune.

   int commune(liste *l1, liste *l2) {
       elem *e1 = l1->tete;
       elem *e2 = l2->tete;
       int n = 0;
       while (e1 != NULL && e2 != NULL) {
           if (e1->valeur == e2->valeur) {
               n = n + 1;
               e1 = e1->next;
               e2 = e2->next;
           } else if (e1->valeur <  e2->valeur) {
               e1 = e1->next;
           } else {
               e2 = e2->next;
           }
       }
       return -1;
   }
   

   END SOLUTION