single - Cree una LinkedList inversa en C++ a partir de una LinkedList determinada

single linked list

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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