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. 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. 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;
  }
}