La position actuelle:Accueil du site>Copier la liste liée avec un pointeur aléatoire < facteur de difficulté>

Copier la liste liée avec un pointeur aléatoire < facteur de difficulté>

2022-05-15 02:11:00Huawei Cloud

Description du sujet:Pour vous donner une longueur de n Liste des liens,Chaque noeud contient un pointeur aléatoire supplémentaire random ,Ce pointeur peut pointer vers n'importe quel noeud de la liste ou un noeud vide.
Construire une copie profonde de cette liste liée. La copie en profondeur doit être faite exactement par n Les nouveaux noeuds,Où la valeur de chaque nouveau noeud est définie à la valeur de son noeud original correspondant.
Nouveau noeud next Pointeur et random Les pointeurs doivent également pointer vers de nouveaux noeuds dans la liste des liens de réplication,Et de faire en sorte que ces pointeurs dans la liste originale et la liste dupliquée représentent le même état de liste liée.Aucun pointeur dans la liste de liens de copie ne doit pointer vers un noeud dans la liste de liens originale .

Par exemple,Si la liste originale contient X Et Y Deux noeuds,Parmi eux X.random --> Y .Donc les deux noeuds correspondants dans la liste de liens de réplication x Et y ,Il y a aussi x.random --> y .Renvoie le noeud d'en - tête de la liste de liens de copie.
Avec un n Une liste de noeuds pour représenter l'entrée/Liste des liens en sortie.Chaque noeud utilise un [val, random_index] Représentation:
val:Une indication Node.val Un entier de.
random_index:Index des noeuds pointés par un pointeur aléatoire(La gamme va de 0 À n-1);Si vous ne pointez vers aucun noeud,Oui. null .
Votre code n'accepte que les noeuds d'en - tête de la liste originale head Comme paramètre entrant.

Exemple1:
Insérer la description de l'image ici

Entrée:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Produits:[[7,null],[13,0],[11,4],[10,2],[1,0]]

Exemple2:
Insérer la description de l'image ici

Entrée:head = [[1,1],[2,1]]
Produits:[[1,1],[2,1]]

Exemple3:
Insérer la description de l'image ici
Entrée:head = [[3,null],[3,0],[3,null]]
Produits:[[3,null],[3,0],[3,null]]

Exemple4:
Entrée:head = [ ]
Produits:[ ]

🧷 Plate - forme:Visual studio 2017 && windows

L'idée centrale:
Pensée 1 (Non réalisé):1,Copiez d'abord chaque noeud de la liste originale,Et relier les nouveaux noeuds (Le noeud de copie n'a pas de relation avec le noeud original);2,Calculer chaque noeud de la liste originalecurDerandomSuivez - moi.curDistance relative de;3,Ensuite, copiez le noeud qui a trouvé la distance relative du noeud courant dans la nouvelle liste de liens,Assigner une valeur àrandom;Cherche.1NoderandomLa complexité temporelle deO(N),Trouver tous les noeudsrandomLa complexité temporelle deO(N^2)

Deuxième idée (Optimiser la pensée 1):1,Après chaque noeud de la liste originale,Lien insérer un noeud de copie (Établir des relations relatives,Cherche.random);2,Positionrandom;3,Détachez le noeud de copie,Lien vers,Restaurer la liste originale en même temps;La complexité temporelle estO(N)

Veuillez ajouter une description de l'image

leetcodeQuestion originale

#include<stdio.h>#include<stdlib.h>struct Node{	int val;	struct Node* next;	struct Node* random;};struct Node* copyRandomList(struct Node* head){	if(head == NULL)        return NULL;	//1.Copier les noeuds derrière chaque noeud original    struct Node* cur = head;    while(cur)    {        //Enregistrer d'abord l'adresse du noeud suivant        struct Node* next = cur->next;        //Évitez l'espace pour copier les noeuds        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));        //Pour garantirvalC'est pareil.        copy->val = cur->val;        //Modifier la relation de lien de la liste de liens originale        cur->next = copy;        copy->next = next;        //Itération        cur = next;    }       //2.Positionrandom    cur = head;    while(cur)    {        //Trouver le noeud de copie        struct Node* copy = cur->next;        //Liensrandom,QuandcurDerandomVide,Traitement spécial requis        if(cur->random)            copy->random = cur->random->next;        else            copy->random = NULL;        //Itération        cur = copy->next;    }    //3.Détachez le noeud de copie,Insérer la queue dans la nouvelle liste(Utilisez le noeud de tête avec la position sentinelle).Restaurer la liste originale en douceur,Bien que le titre n'exige pas    struct Node *copyhead, *copytail;    copyhead = copytail = (struct Node*)malloc(sizeof(struct Node));    cur = head;    while(cur)    {        //Trouver le noeud de copie        struct Node* copy = cur->next;         //Enregistrer l'adresse du noeud suivant de la liste originale        struct Node* next = copy->next;        //Insertion caudale        copytail->next = copy;        copytail = copy;        //Restaurer la liste originale        cur->next = next;        //Itération        cur = next;    }    //4.Libérer de l'espace    struct Node* temp = copyhead;    copyhead = copyhead->next;    free(temp);    return copyhead;}int main(){	struct Node* n1 = (struct Node*)malloc(sizeof(struct Node));	n1->val = 3;	struct Node* n2 = (struct Node*)malloc(sizeof(struct Node));	n2->val = 3;		struct Node* n3 = (struct Node*)malloc(sizeof(struct Node));	n3->val = 3;	n1->next = n2;	n2->next = n3;	n3->next = NULL;		n1->random = n3;	n2->random = n1;	n3->random = NULL;		copyRandomList(n1);	return 0;}

Veuillez ajouter une description de l'image

Mentions de copyright
Auteur de cet article [Huawei Cloud],Réimpression s’il vous plaît apporter le lien vers l’original, merci
https://fra.chowdera.com/2022/135/202205142058343961.html

Recommandé au hasard