Revertir lista recursivamente en C++

publicado por: Anonymous

Estoy tratando de revertir una lista recursivamente. El problema es cuando la función recursiva llega al caso base.Esta debería devolver un puntero al ultimo elemento de la lista. Si imprimo el puntero antes del retorno(dentro de la función) el valor es el correcto, pero una vez retornado el puntero apunta a el primer elemento.

#include <iostream>

using namespace std;

struct Node{
  int dato;
  Node * sig;
};

void insert(Node * &list,int d){
  Node * newNode=new Node();
  newNode->dato=d;
  newNode->sig=0;

  if(list==0){

    list=newNode;
    return;

  }

  newNode->sig=list;
  list=newNode;
}

void print(Node * list){
  Node * temp=list;

  while(temp!=0){

    cout<< temp->dato<<endl;
    temp=temp->sig;
  }
}

Node * reverse(Node * list){
  Node* ptr = list;

  if(list->sig!=0){
    ptr = reverse(list->sig);

    (list->sig)->sig=list;
    list->sig=0;
  }

  return ptr;
}

int main(){
  Node * l = 0; //creo la cabeza de la lista

  insert(l,3);// cargo 3 valores
  insert(l,2);
  insert(l,1);

  l=reverse(l); // la cabeza de la lista apunta al ultimo elemento retornado por reverse()

  print(l);

  system("PAUSE");
  return 0;
}

solución

Node * reverse(Node * list)
{
  if(list->sig==0)
  {
    // cout->list; Si imprimo acá el valor es el correcto
    return list; // al retornar el valor cambia
  }

  reverse(list->sig);

  (list->sig)->sig=list;
  list->sig=0;
}

Esta función, desde el momento en el que no finaliza return ya está mal implementada. Aun así vamos a analizar su comportamiento:

  • reverse(1) -> list => 1
  • list->sig == 2 (no entra en el if)
  • reverse(2) -> list => 2
    • list->sig == 3 (no entra en el if)
    • reverse(3) -> list => 3
      • list->sig == 0 (entra en el if)
      • return 3
    • (*1)
    • list->sig->sig = list -> 2->3->sig = 2
    • list->sig = 0 -> 2->sig = 0
    • (no hay return) ERROR!!!
  • list->sig->sig = list -> 1->2->sig = 2
  • list->sig = 0 -> 1->sig = 0
  • (no hay return) ERROR!!!

La teoría estaría bien… pero te falta retornar el puntero al nuevo primer elemento de la lista y ese puntero lo has perdido en (*1). Una vez has perdido dicho puntero ya no hay vuelta atrás porque la lista, al ser simple, no tienes ningún puntero que te permita acceder a dicho nodo.

¿Solución? Un par de retoques tontos:

Node * reverse(Node * list)
{
  Node* ptr = list;

  if(list->sig!=0)
  {
    ptr = reverse(list->sig);

    (list->sig)->sig=list;
    list->sig=0;
  }

  return ptr;
}

La mecánica es muy simple… el valor a retornar por la función será uno de los siguientes:

  • Si el nodo actual no es el último nodo de la lista, lo que devuelva la llamada recursiva.
  • Si el nodo actual es el último se devuelve dicho nodo.

De esta forma te garantizas que la función te devuelve el nodo al primer nodo de la lista invertida.

Respondido por: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *