single - Cree una LinkedList inversa en C++ a partir de una LinkedList determinada
single linked list (9)
Más fácil: revise su lista vinculada, guarde el nodo anterior y el siguiente y simplemente deje que el nodo actual apunte al anterior:
void LinkedList::reversedLinkedList()
{
if(head == NULL) return;
Node *prev = NULL, *current = NULL, *next = NULL;
current = head;
while(current != NULL){
next = current->next;
current->next = prev;
prev = current;
current = next;
}
// now let the head point at the last node (prev)
head = prev;
}
Tengo problemas para crear una lista enlazada en orden inverso desde una lista enlazada determinada.
Vengo de un pasado de Java, y acabo de empezar a hacer algo de C ++.
¿Puedes revisar mi código y ver qué pasa? Supongo que solo estoy manipulando el puntero y no creando nada nuevo.
//this is a method of linkedlist class, it creates a reverse linkedlist
//and prints it
void LinkedList::reversedLinkedList()
{
Node* revHead;
//check if the regular list is empty
if(head == NULL)
return;
//else start reversing
Node* current = head;
while(current != NULL)
{
//check if it''s the first one being added
if(revHead == NULL)
revHead = current;
else
{
//just insert at the beginning
Node* tempHead = revHead;
current->next = tempHead;
revHead = current;
}
current = current->next;
}//end while
//now print it
cout << "Reversed LinkedList: " << endl;
Node* temp = revHead;
while(temp != NULL)
{
cout << temp->firstName << endl;
cout << temp->lastName << endl;
cout << endl;
temp = temp->next;
}
}//end method
Node* revHead;
// ...
while(current != NULL)
{
//check if it''s the first one being added
if(revHead == NULL)
No inicializas revHead pero lo usas. (Espero que ya esté claro para usted que revHead es una variable local utilizada para almacenar una dirección de memoria, y no algo que exista fuera del método / procedimiento)
La clase de almacenamiento de revHead es automática (también conocida como scope-body local). En C++ cuando haces una declaración como esa, no hay garantía de que el valor sea 0 .
(a menos que la clase de almacenamiento sea de tipo static o la variable sea global donde se inicializa automáticamente a 0 si no se proporciona ningún otro valor. En su caso, la variable tiene una clase de almacenamiento de tipo auto que significa que está definida localmente en una función y al declarar una variable local, sin especificar un valor, el valor es basura. Tenga en cuenta que con el siguiente estándar de C++0x la palabra clave auto tiene un nuevo significado).
El valor en su caso es basura, lo que hace que el if falla. Ver más información aquí: Enlace
Haz un
Node* revHead = NULL;
Tenga en cuenta que tal vez también pueda tener errores como ese en otras partes de su código.
Otro método sería cruzar primero la lista y almacenar todos los datos en una pila, luego crear una nueva lista e insertar datos en ella desde la parte superior de la pila. Al ser LIFO, le dará los datos en orden inverso y, por lo tanto, tendrá una lista invertida
No estoy seguro, pero creo que quieres una lista doblemente unida donde el nodo tiene una próxima y anterior. No funcionará con un puntero externo a la lista. No tendrá la dirección del nodo anterior.
Si no utiliza el método de arriba con una pila, es una buena sugerencia.
Esto se hace usando solo dos variables temporales.
Node* list::rev(Node *first)
{
Node *a = first, *b = first->next;
while(a->next!=NULL)
{
b = a->next;
a->next = a->next->next;
b->next = first;
first = b;
}
return first;
}
Además, puedes hacer esto usando la recursión.
NODE * ReverseLinkedList(NODE * head){
if (head == NULL)
return NULL;
NODE * previous = NULL;
while (head != NULL) {
// Keep next node since we trash the next pointer.
NODE *next = head->pNext;
// Switch the next pointer to point backwards.
head->pNext = previous;
// Move both pointers forward.
previous = head;
head = next;
}
return previous;
}
El ejemplo siguiente utiliza la recursión para invertir una lista de enlaces. Le pregunté a este Qs en una entrevista de trabajo. Esto ha sido probado y funciona. ListElem es el nodo.
void LinkList::reverse()
{
if(pFirst == NULL) return;
ListElem* current = pFirst;
revCur(NULL, current, NULL);
}
void LinkList::revCur(ListElem *prev, ListElem* current, ListElem* next)
{
// ListElem *prev = NULL, *current = NULL, *next = NULL;
if ( current != NULL )
{
next = current->next;
current->next = prev;
prev = current;
current = next;
pFirst = prev;
this->revCur(prev,current,next);
}
}
Lo anterior es un reverso de la lista de enlaces
void LinkList::rev()
{
if(pFirst == NULL) return;
ListElem *prev = NULL, *current = NULL, *next = NULL;
current = pFirst;
while(current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
// now let the head point at the last node (prev)
pFirst = prev;
}
#include <stdint.h>
/*
this is a generic (structure agnostic) routine for reversing a singly linked list.
1st argument is the memory address the structure is located at, and
2nd argument is the memory address to this particular structure''s NEXT member.
*/
void *rsll(void *struct_address, void *next_address /*(void **)*/)
{
uint32_t offset, holder;
offset = next_address - struct_address;
void **p = struct_address, *progress = NULL;
while(p)
{
void *b;
holder = (uint32_t)p;
holder += offset;
p = (void**)holder; //&(N->next)
b = *p; //(N->next)
*p = progress; //(N->next)
holder = (uint32_t)p;
holder -= offset;
p = (void**)holder; //N
progress = p;
p = b;
}
return progress;
}
#include <stdio.h>
int
main()
{
struct list_t
{
int integer;
struct list_t *next;
};
struct list_t d = {40,NULL},
c = {30,&d},
b = {23,&c},
a = {10,&b};
struct list_t *list;
list = &a;
list = rsll(list,&(list->next));
while(list)
{
printf("%d/n",list->integer);
list = list->next;
}
return 0;
}