[JAVA] Gymnastique algorithmique 15

Merge Two Sorted Linked Lists (Easy)

La description

Une liste à liaison unique triée par ordre croissant est transmise comme argument. Un algorithme qui fusionne les deux et renvoie la tête de la liste liée triée par ordre croissant comme valeur de retour.

Exemple

Il existe deux listes liées comme ci-dessous. Screen Shot 2020-01-11 at 13.08.56.png Lorsque ces deux listes liées sont fusionnées tout en conservant le tri, elles deviennent une seule liste liée comme indiqué ci-dessous. Screen Shot 2020-01-11 at 13.10.58.png Solution Runtime Complexity O(m + n) Puisqu'il utilise deux pointeurs pour effectuer un balayage linéaire sur deux listes liées Avec m et n comme longueur de chaque liste liée, le temps d'exécution est O (m + n).

Space Complexity O(1) La mémoire est O (1) car elle est utilisée pour le pointeur.

la mise en oeuvre

MergeSortList.java


class mergeSortList{
  public LinkedListNode merge_sorted(LinkedListNode head1,LinkedListNode head2) {


    if (head1 == null) { // edge case
      return head2;
    } else if (head2 == null) {
      return head1;
    }
    
    LinkedListNode cur1 = head1; // pointer1
    LinkedListNode cur2 = head2; // pointer2
    LinkedListNode cur3 = null; // pointer3 for merged list
    LinkedListNode head3 = null; // head of merged list

    while (cur1 != null && cur1 != null) {
      if (head3 == null) {
        if (cur1.data < cur2.data) {
          head3 = cur1;
          cur1 = cur1.next;
        } else {
          head3 = cur2;
          cur2 = cur2.next;
        }
        cur3 = head3;
      } else {
        if (cur1.data < cur2.data) {
          cur3.next = cur1;
          cur1 = cur1.next;
        } else {
          cur3.next = cur2;
          cur2 = cur2.next;
        }
        cur3 = cur3.next;
      }
    }
    
    if (cur1 != null) {
      cur3.next = cur1;
    } else {
      cur3.next = cur2;
    }
  
    return head3;
  }
}


Recommended Posts

Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 23 Intervalles de fusion
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Exercice d'algorithme 6
Gymnastique algorithmique 24 Inverser une liste liée
Algorithme Python
Exercices d'algorithme 13
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Gymnastique algorithmique 24 Milieu de la liste liée
Mémorandum Python (algorithme)
Algorithme d'apprentissage du dictionnaire
Algorithme de recherche de chaînes