CLONER UNE LISTE CHAÎNÉE AVEC UN POINTEUR SUIVANT ET ALÉATOIRE DANS L'ESPACE O (1)

Compte tenu d'un liste chaînée de taille N où chaque nœud a deux liens : pointeur suivant pointant vers le nœud suivant et pointeur aléatoire à n’importe quel nœud aléatoire de la liste. La tâche consiste à créer un clone de cette liste chaînée dans l'espace O(1), c'est-à-dire sans espace supplémentaire.

Exemples :

Saisir: Tête de la liste ci-dessous

Sortir: Une nouvelle liste chaînée identique à la liste originale.

[Approche attendue] En insérant des nœuds sur place – O(3n) Time et O(1) Space

L'idée est de créer un double d'un nœud et au lieu de le stocker dans une table de hachage séparée, nous pouvons l'insérer entre le nœud d'origine et le nœud suivant. Nous aurons désormais de nouveaux nœuds à des positions alternatives. Maintenant pour un nœud X son duplicata sera X->suivant et le pointeur aléatoire du double doit pointer vers X->aléatoire->suivant (car c'est le double de X->aléatoire ). Par conséquent, parcourez toute la liste chaînée pour mettre à jour le pointeur aléatoire de tous les nœuds clonés, puis répétez à nouveau pour séparer la liste chaînée d'origine et la liste chaînée clonée.

Suivez les étapes mentionnées ci-dessous pour mettre en œuvre l'idée :

Créer la copie de nœud 1 et insérez-le entre nœud 1 et nœud 2 dans la liste chaînée d'origine, créez la copie de nœud 2 et insérez-le entre 2 ^sd et 3 ^rd nœud et ainsi de suite. Ajouter la copie de N après le N ^ème nœud
Connectez le nœud clone en mettant à jour les pointeurs aléatoires.
Séparez la liste chaînée clonée de la liste d'origine en mettant à jour les pointeurs suivants.

Cloner une liste chaînée avec un pointeur suivant et aléatoire dans l

Vous trouverez ci-dessous la mise en œuvre de l'approche ci-dessus :

C++

    // C++ code to Clone a linked list with next and random   // pointer by Inserting Nodes In-place   #include          using     namespace     std  ;   struct     Node     {      int     data  ;      Node     *  next       *  random  ;      Node  (  int     x  )     {      data     =     x  ;      next     =     random     =     NULL  ;      }   };   Node  *     cloneLinkedList  (  Node  *     head  )     {      if     (  head     ==     NULL  )     {      return     NULL  ;      }          // Create new nodes and insert them next to       // the original nodes      Node  *     curr     =     head  ;      while     (  curr     !=     NULL  )     {      Node  *     newNode     =     new     Node  (  curr  ->  data  );      newNode  ->  next     =     curr  ->  next  ;      curr  ->  next     =     newNode  ;      curr     =     newNode  ->  next  ;      }          // Set the random pointers of the new nodes      curr     =     head  ;      while     (  curr     !=     NULL  )     {      if     (  curr  ->  random     !=     NULL  )      curr  ->  next  ->  random     =     curr  ->  random  ->  next  ;      curr     =     curr  ->  next  ->  next  ;      }          // Separate the new nodes from the original nodes      curr     =     head  ;      Node  *     clonedHead     =     head  ->  next  ;      Node  *     clone     =     clonedHead  ;      while     (  clone  ->  next     !=     NULL  )     {          // Update the next nodes of original node       // and cloned node      curr  ->  next     =     curr  ->  next  ->  next  ;      clone  ->  next     =     clone  ->  next  ->  next  ;          // Move pointers of original as well as       // cloned linked list to their next nodes      curr     =     curr  ->  next  ;      clone     =     clone  ->  next  ;      }      curr  ->  next     =     NULL  ;      clone  ->  next     =     NULL  ;          return     clonedHead  ;   }   // Function to print the linked list   void     printList  (  Node  *     head  )     {      while     (  head     !=     NULL  )     {      cout      < <     head  ->  data      < <     '('  ;      if  (  head  ->  random  )      cout      < <     head  ->  random  ->  data      < <     ')'  ;      else         cout      < <     'null'      < <     ')'  ;          if  (  head  ->  next     !=     NULL  )      cout      < <     ' -> '  ;      head     =     head  ->  next  ;      }      cout      < <     endl  ;   }   int     main  ()     {          // Creating a linked list with random pointer      Node  *     head     =     new     Node  (  1  );      head  ->  next     =     new     Node  (  2  );      head  ->  next  ->  next     =     new     Node  (  3  );      head  ->  next  ->  next  ->  next     =     new     Node  (  4  );      head  ->  next  ->  next  ->  next  ->  next     =     new     Node  (  5  );      head  ->  random     =     head  ->  next  ->  next  ;      head  ->  next  ->  random     =     head  ;      head  ->  next  ->  next  ->  random     =     head  ->  next  ->  next  ->  next  ->  next  ;      head  ->  next  ->  next  ->  next  ->  random     =     head  ->  next  ->  next  ;      head  ->  next  ->  next  ->  next  ->  next  ->  random     =     head  ->  next  ;          // Print the original list      cout      < <     'Original linked list:  n  '  ;      printList  (  head  );          // Function call      Node  *     clonedList     =     cloneLinkedList  (  head  );          cout      < <     'Cloned linked list:  n  '  ;      printList  (  clonedList  );          return     0  ;   }

Java

    // Java code to Clone a linked list with next and random   // pointer by Inserting Nodes In-place   class   Node     {      int     data  ;      Node     next       random  ;          Node  (  int     x  )     {      data     =     x  ;      next     =     random     =     null  ;      }   }   class   GfG     {          // Function to clone the linked list      static     Node     cloneLinkedList  (  Node     head  )     {      if     (  head     ==     null  )     {      return     null  ;      }          // Create new nodes and insert them next to the original nodes      Node     curr     =     head  ;      while     (  curr     !=     null  )     {      Node     newNode     =     new     Node  (  curr  .  data  );      newNode  .  next     =     curr  .  next  ;      curr  .  next     =     newNode  ;      curr     =     newNode  .  next  ;      }          // Set the random pointers of the new nodes      curr     =     head  ;      while     (  curr     !=     null  )     {      if     (  curr  .  random     !=     null  )     {      curr  .  next  .  random     =     curr  .  random  .  next  ;      }      curr     =     curr  .  next  .  next  ;      }          // Separate the new nodes from the original nodes      curr     =     head  ;      Node     clonedHead     =     head  .  next  ;      Node     clone     =     clonedHead  ;      while     (  clone  .  next     !=     null  )     {      // Update the next nodes of original node      // and cloned node      curr  .  next     =     curr  .  next  .  next  ;      clone  .  next     =     clone  .  next  .  next  ;          // Move pointers of original and cloned      // linked list to their next nodes      curr     =     curr  .  next  ;      clone     =     clone  .  next  ;      }      curr  .  next     =     null  ;      clone  .  next     =     null  ;          return     clonedHead  ;      }          // Function to print the linked list      public     static     void     printList  (  Node     head  )     {      while     (  head     !=     null  )     {      System  .  out  .  print  (  head  .  data     +     '('  );      if     (  head  .  random     !=     null  )     {      System  .  out  .  print  (  head  .  random  .  data  );      }     else     {      System  .  out  .  print  (  'null'  );      }      System  .  out  .  print  (  ')'  );          if     (  head  .  next     !=     null  )     {      System  .  out  .  print  (  ' -> '  );      }      head     =     head  .  next  ;      }      System  .  out  .  println  ();      }          public     static     void     main  (  String  []     args  )     {          // Creating a linked list with random pointer      Node     head     =     new     Node  (  1  );      head  .  next     =     new     Node  (  2  );      head  .  next  .  next     =     new     Node  (  3  );      head  .  next  .  next  .  next     =     new     Node  (  4  );      head  .  next  .  next  .  next  .  next     =     new     Node  (  5  );      head  .  random     =     head  .  next  .  next  ;      head  .  next  .  random     =     head  ;      head  .  next  .  next  .  random     =     head  .  next  .  next  .  next  .  next  ;      head  .  next  .  next  .  next  .  random     =     head  .  next  .  next  ;      head  .  next  .  next  .  next  .  next  .  random     =     head  .  next  ;          // Print the original list      System  .  out  .  println  (  'Original linked list:'  );      printList  (  head  );          // Function call      Node     clonedList     =     cloneLinkedList  (  head  );          System  .  out  .  println  (  'Cloned linked list:'  );      printList  (  clonedList  );      }   }

Python

    # Python code to Clone a linked list with next and random   # pointer by Inserting Nodes In-place   class   Node  :   def   __init__  (  self     x  ):   self  .  data   =   x   self  .  next   =   None   self  .  random   =   None   # Function to clone the linked list   def   clone_linked_list  (  head  ):   if   head   is   None  :   return   None   # Create new nodes and insert them next to    # the original nodes   curr   =   head   while   curr   is   not   None  :   new_node   =   Node  (  curr  .  data  )   new_node  .  next   =   curr  .  next   curr  .  next   =   new_node   curr   =   new_node  .  next   # Set the random pointers of the new nodes   curr   =   head   while   curr   is   not   None  :   if   curr  .  random   is   not   None  :   curr  .  next  .  random   =   curr  .  random  .  next   curr   =   curr  .  next  .  next   # Separate the new nodes from the original nodes   curr   =   head   cloned_head   =   head  .  next   clone   =   cloned_head   while   clone  .  next   is   not   None  :   # Update the next nodes of original node    # and cloned node   curr  .  next   =   curr  .  next  .  next   clone  .  next   =   clone  .  next  .  next   # Move pointers of original as well as    # cloned linked list to their next nodes   curr   =   curr  .  next   clone   =   clone  .  next   curr  .  next   =   None   clone  .  next   =   None   return   cloned_head   # Function to print the linked list   def   print_list  (  head  ):   while   head   is   not   None  :   print  (  f  '  {  head  .  data  }  ('     end  =  ''  )   if   head  .  random  :   print  (  f  '  {  head  .  random  .  data  }  )'     end  =  ''  )   else  :   print  (  'null)'     end  =  ''  )   if   head  .  next   is   not   None  :   print  (  ' -> '     end  =  ''  )   head   =   head  .  next   print  ()   if   __name__   ==   '__main__'  :   # Creating a linked list with random pointer   head   =   Node  (  1  )   head  .  next   =   Node  (  2  )   head  .  next  .  next   =   Node  (  3  )   head  .  next  .  next  .  next   =   Node  (  4  )   head  .  next  .  next  .  next  .  next   =   Node  (  5  )   head  .  random   =   head  .  next  .  next   head  .  next  .  random   =   head   head  .  next  .  next  .  random   =   head  .  next  .  next  .  next  .  next   head  .  next  .  next  .  next  .  random   =   head  .  next  .  next   head  .  next  .  next  .  next  .  next  .  random   =   head  .  next   # Print the original list   print  (  'Original linked list:'  )   print_list  (  head  )   # Function call   cloned_list   =   clone_linked_list  (  head  )   print  (  'Cloned linked list:'  )   print_list  (  cloned_list  )

    // C# code to Clone a linked list with next and random   // pointer by Inserting Nodes In-place   using     System  ;   using     System.Collections.Generic  ;   public     class     Node     {      public     int     Data  ;      public     Node     next       Random  ;      public     Node  (  int     x  )     {      Data     =     x  ;      next     =     Random     =     null  ;      }   }   class     GfG     {      static     Node     CloneLinkedList  (  Node     head  )     {      if     (  head     ==     null  )      return     null  ;      // Create new nodes and insert them next to       // the original nodes      Node     curr     =     head  ;      while     (  curr     !=     null  )     {      Node     newNode     =     new     Node  (  curr  .  Data  );      newNode  .  next     =     curr  .  next  ;      curr  .  next     =     newNode  ;      curr     =     newNode  .  next  ;      }      // Set the random pointers of the new nodes      curr     =     head  ;      while     (  curr     !=     null  )     {      if     (  curr  .  Random     !=     null  )      curr  .  next  .  Random     =     curr  .  Random  .  next  ;      curr     =     curr  .  next  .  next  ;      }      // Separate the new nodes from the original nodes      curr     =     head  ;      Node     clonedHead     =     head  .  next  ;      Node     clone     =     clonedHead  ;      while     (  clone  .  next     !=     null  )     {          // Update the next nodes of original node       // and cloned node      curr  .  next     =     curr  .  next  .  next  ;      clone  .  next     =     clone  .  next  .  next  ;      // Move pointers of original as well as       // cloned linked list to their next nodes      curr     =     curr  .  next  ;      clone     =     clone  .  next  ;      }      curr  .  next     =     null  ;      clone  .  next     =     null  ;      return     clonedHead  ;      }      // Function to print the linked list      static     void     PrintList  (  Node     head  )     {      while     (  head     !=     null  )     {      Console  .  Write  (  head  .  Data     +     '('  );      if     (  head  .  Random     !=     null  )      Console  .  Write  (  head  .  Random  .  Data     +     ')'  );      else      Console  .  Write  (  'null)'  );          if     (  head  .  next     !=     null  )      Console  .  Write  (  ' -> '  );      head     =     head  .  next  ;      }      Console  .  WriteLine  ();      }      public     static     void     Main  ()     {          // Creating a linked list with random pointer      Node     head     =     new     Node  (  1  );      head  .  next     =     new     Node  (  2  );      head  .  next  .  next     =     new     Node  (  3  );      head  .  next  .  next  .  next     =     new     Node  (  4  );      head  .  next  .  next  .  next  .  next     =     new     Node  (  5  );      head  .  Random     =     head  .  next  .  next  ;      head  .  next  .  Random     =     head  ;      head  .  next  .  next  .  Random     =     head  .  next  .  next  .  next  .  next  ;      head  .  next  .  next  .  next  .  Random     =     head  .  next  .  next  ;      head  .  next  .  next  .  next  .  next  .  Random     =     head  .  next  ;      // Print the original list      Console  .  WriteLine  (  'Original linked list:'  );      PrintList  (  head  );      Node     clonedList     =     CloneLinkedList  (  head  );      Console  .  WriteLine  (  'Cloned linked list:'  );      PrintList  (  clonedList  );      }   }

JavaScript

    // JavaScript code to Clone a linked list with next and random   // pointer by Inserting Nodes In-place   class     Node     {      constructor  (  data  )     {      this  .  data     =     data  ;      this  .  next     =     null  ;      this  .  random     =     null  ;      }   }   function     cloneLinkedList  (  head  )     {      if     (  head     ===     null  )     {      return     null  ;      }      // Create new nodes and insert them next to the       // original nodes      let     curr     =     head  ;      while     (  curr     !==     null  )     {      let     newNode     =     new     Node  (  curr  .  data  );      newNode  .  next     =     curr  .  next  ;      curr  .  next     =     newNode  ;      curr     =     newNode  .  next  ;      }      // Set the random pointers of the new nodes      curr     =     head  ;      while     (  curr     !==     null  )     {      if     (  curr  .  random     !==     null  )     {      curr  .  next  .  random     =     curr  .  random  .  next  ;      }      curr     =     curr  .  next  .  next  ;      }      // Separate the new nodes from the original nodes      curr     =     head  ;      let     clonedHead     =     head  .  next  ;      let     clone     =     clonedHead  ;      while     (  clone  .  next     !==     null  )     {          // Update the next nodes of original node and cloned node      curr  .  next     =     curr  .  next  .  next  ;      clone  .  next     =     clone  .  next  .  next  ;      // Move pointers of original as well as cloned      // linked list to their next nodes      curr     =     curr  .  next  ;      clone     =     clone  .  next  ;      }      curr  .  next     =     null  ;      clone  .  next     =     null  ;      return     clonedHead  ;   }   // Function to print the linked list   function     printList  (  head  )     {      let     result     =     ''  ;      while     (  head     !==     null  )     {      result     +=     head  .  data     +     '('  ;      result     +=     head  .  random     ?     head  .  random  .  data     :     'null'  ;      result     +=     ')'  ;      if     (  head  .  next     !==     null  )     {      result     +=     ' -> '  ;      }      head     =     head  .  next  ;      }      console  .  log  (  result  );   }   // Creating a linked list with random pointer   let     head     =     new     Node  (  1  );   head  .  next     =     new     Node  (  2  );   head  .  next  .  next     =     new     Node  (  3  );   head  .  next  .  next  .  next     =     new     Node  (  4  );   head  .  next  .  next  .  next  .  next     =     new     Node  (  5  );   head  .  random     =     head  .  next  .  next  ;   head  .  next  .  random     =     head  ;   head  .  next  .  next  .  random     =     head  .  next  .  next  .  next  .  next  ;   head  .  next  .  next  .  next  .  random     =     head  .  next  .  next  ;   head  .  next  .  next  .  next  .  next  .  random     =     head  .  next  ;   // Print the original list   console  .  log  (  'Original linked list:'  );   printList  (  head  );   let     clonedList     =     cloneLinkedList  (  head  );   console  .  log  (  'Cloned linked list:'  );   printList  (  clonedList  );

Sortir

Original linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2) Cloned linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2)

Complexité temporelle : O(3n) parce que nous parcourons la liste chaînée trois fois.
Espace auxiliaire : O(1) comme nous stockons tous les nœuds clonés dans la liste chaînée d'origine elle-même, aucun espace supplémentaire n'est requis.

Créer un quiz