lista enlazada: Esta es una lista enlazada que queremos invertir.
Después de la lista enlazada invertida: El siguiente será el resultado después de invertir la lista vinculada anteriormente.
En el diagrama de ejemplo anterior, podemos ver que el nodo principal y el nodo final cambian sus posiciones cuando invertimos la lista enlazada. El nodo principal, que ahora es un nodo final, apunta al nodo nulo porque ahora es un nodo final.
Pasos del algoritmo
- Creamos un método principal y declaramos algunas variables requeridas.
- Luego, nuestro próximo paso es crear un método que pueda crear una lista enlazada. Este método nos ayuda a crear una lista enlazada.
- El siguiente paso es crear un método para invertir la lista enlazada. En este método, pasamos toda la lista enlazada y este método invertirá la lista enlazada.
- Ahora, necesitamos otro método para mostrar nuestro resultado después de invertirlo.
- Combinaremos todos estos métodos anteriores en nuestro método principal.
Vamos a explicar la lista de enlaces invertidos usando alguna forma pictórica para que sea más fácil de entender. Entonces, comencemos con el ejemplo.
La siguiente es una lista enlazada que queremos invertir.
Paso 1 . El nodo de color verde es un nodo principal, que apunta al primer nodo en el inicio.
Paso 2. En el siguiente paso, recorreremos toda la lista enlazada hasta que no obtengamos el puntero nulo al lado del nodo de encabezado. Para eso, vamos a asignar al siguiente nodo un nombre temporal, como se muestra en el siguiente diagrama.
Paso 3. Como tenemos un nuevo nodo de referencia llamado 'temporal', que puede ayudarnos a recorrer toda la lista enlazada hasta que no obtengamos el puntero nulo, podemos establecer el siguiente enlace del nodo de encabezado como nulo, lo que no afectará el enlace. lista como se muestra a continuación en el diagrama. El puntero nulo junto al nodo actual se denomina nodo anterior.
Paso 4. Ahora, movemos el nodo temporal al siguiente nodo y el nodo actual al nodo temporal anterior. Así que ahora nos hemos movido al siguiente nodo. También cambiamos el nodo anterior de nulo a solo el nodo anterior del nodo actual. Así que ahora el nodo temporal se encargará de todos los cruces hasta el puntero nulo para que podamos establecer el vínculo del nodo actual con el nodo anterior, y ahora apunta al nodo anterior, como se muestra en el siguiente diagrama.
Así que seguimos los mismos pasos y, por fin, obtendremos una lista enlazada invertida.
Paso 5 .
Paso 6.
Paso 7.
Paso 8.
Paso 9.
Paso 10.
Paso 11.
Paso 12.
Paso 13.
Paso 14. En este paso, nuestra lista enlazada se invirtió.
Programa en C++ para invertir una lista enlazada
#incluirusando espacio de nombres estándar ;
// Método para crear el nodo
estructura nodo {
En t valor ;
nodo * nextNodePtr ;
} * nodoObjeto ;
vacío crearListaEnlazada ( En t norte ) ;
vacío lista enlazada inversa ( nodo ** nodoObjeto ) ;
vacío monitor ( ) ;
En t principal ( ) {
En t n,valor,elemento ;
cout << 'Cuántos nodos quieres crear =>:' ;
comiendo >> norte ;
crearListaEnlazada ( norte ) ;
cout << ' \norte Información en la lista enlazada: \norte ' ;
monitor ( ) ;
cout << ' \norte Lista enlazada después de invertir \norte ' ;
lista enlazada inversa ( & nodoObjeto ) ;
monitor ( ) ;
devolver 0 ;
}
// Este método creará la lista enlazada
vacío crearListaEnlazada ( En t norte ) {
estructura nodo * nodo frontal, * nodo temporal ;
En t valor, yo ;
nodoObjeto = ( estructura nodo * ) malloc ( tamaño de ( estructura nodo ) ) ;
si ( nodoObjeto == NULO )
cout << 'No es suficiente para perder la memoria' ;
más {
cout << 'Ingrese la información del nodo 1 (solo número):' ;
comiendo >> valor ;
nodoObjeto - > valor = valor ;
nodoObjeto - > nextNodePtr = NULO ;
nodo temporal = nodoObjeto ;
por ( i = 2 ; i <= norte ; i ++ ) {
nodo frontal = ( estructura nodo * ) malloc ( tamaño de ( estructura nodo ) ) ;
// Cuando no hay ningún nodo en la lista enlazada
si ( nodo frontal == NULO ) {
cout << 'No se puede asignar memoria' ;
descanso ;
}
más {
cout << 'Por favor ingrese la información del nodo' << i << ': ' ;
comiendo >> valor ;
nodo frontal - > valor = valor ;
nodo frontal - > nextNodePtr = NULO ;
nodo temporal - > nextNodePtr = nodo frontal ;
nodo temporal = nodo temporal - > nextNodePtr ;
}
}
}
}
vacío lista enlazada inversa ( nodo ** nodoObjeto ) {
estructura nodo * nodo temporal = NULO ;
estructura nodo * nodo anterior = NULO ;
estructura nodo * nodoactual = ( * nodoObjeto ) ;
tiempo ( nodoactual ! = NULO ) {
nodo temporal = nodoactual - > nextNodePtr ;
nodoactual - > nextNodePtr = nodo anterior ;
nodo anterior = nodoactual ;
nodoactual = nodo temporal ;
}
( * nodoObjeto ) = nodo anterior ;
}
vacío monitor ( ) {
estructura nodo * nodo temporal ;
si ( nodoObjeto == NULO ) {
cout << 'La lista enlazada está vacía' ;
}
más {
nodo temporal = nodoObjeto ;
tiempo ( nodo temporal ! = NULO )
{
cout << nodo temporal - > valor << ' \t ' ;
nodo temporal = nodo temporal - > nextNodePtr ;
}
}
cout << final ;
}
Producción
Cuantos nodos quieres crear =>: 6Ingrese la información del nodo 1 (solo número): 101
Ingrese la información del nodo 2: 95
Ingrese la información del nodo 3: 61
Por favor ingrese la información del nodo 4: 19
Por favor ingrese la información del nodo 5: 12
Por favor ingrese la información del nodo 6: 11
Información en la lista enlazada:
101 95 61 19 12 11
Lista enlazada después de invertir
11 12 19 61 95 101
Conclusión
Este artículo de LinuxHint ha revisado cómo revertir una lista enlazada en C++. Existen otros métodos para invertir una lista vinculada, pero este es un método muy común para invertir una lista vinculada. Depende de usted decidir cómo quiere resolver sus problemas, pero generalmente la función de lista de enlaces inversos debe ser un ciclo simple con intercambios de punteros.