Reverse list recursively in C ++

4

I am trying to revert a list recursively. The problem is when the recursive function arrives at the base case. This should return a pointer to the last element in the list. If I print the pointer before the return (inside the function) the value is correct, but once returned the pointer points to the first element.

#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;
}
    
asked by Juan 02.02.2017 в 01:22
source

2 answers

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

This function, from the moment when return is not finished, is already poorly implemented. Even so, we are going to analyze its behavior:

  • reverse(1) - > list = > 1
  • list->sig == 2 (does not enter the if)
  • reverse(2) - > list = > two
    • list->sig == 3 (does not enter the if)
    • reverse(3) - > list = > 3
      • list->sig == 0 (enters the if)
      • return 3
    • (* 1)
    • list->sig->sig = list - > 2-> 3-> sig = 2
    • list->sig = 0 - > 2-> sig = 0
    • (no return) ERROR !!!
  • list->sig->sig = list - > 1-> 2-> sig = 2
  • list->sig = 0 - > 1- > sig = 0
  • (no return) ERROR !!!

The theory would be fine ... but you need to return the pointer to the new first item in the list and that pointer you have lost in (* 1). Once you have lost that pointer there is no going back because the list, being simple, you do not have any pointer that allows you to access that node.

Solution? A couple of silly touches:

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

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

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

  return ptr;
}

The mechanics are very simple ... the value to return for the function will be one of the following:

  • If the current node is not the last node in the list, which returns the recursive call.
  • If the current node is the last one, that node is returned.

This way you guarantee that the function returns the node to the first node of the inverted list.

    
answered by 02.02.2017 / 09:10
source
2

I do not understand what you mean by " revert " a list Do you mean to order it in an inverse way?.

Be that as it may, your recursion is useless. The function reverse returns a pointer to Node , but you do not use that return at all. You only return a Node when you have reached the last node, in the rest of cases you do not return anything and the function ends ... what is a undefined behavior .

Node * reverse(Node * list){
    if(list->sig==0){
        // Devuelves el nodo que no apunta a un siguiente
        // es decir: el ultimo nodo.
        return list;
    }

    // Llamas recursivamente a la funcion Y NO RECOGES EL VALOR DE RETORNO
    reverse(list->sig);

    (list->sig)->sig=list;
    list->sig=0;
} // FINALIZAS LA FUNCION SIN DEVOLVER NINGUN VALOR!!!!

Your nodes are structured like this:

And what is happening?

  • We call reverse with NodoA .
  • NodeA ->sig is not 0 (is NodeB ), the if is not met.
  • You call reverse with NodeA ->sig which is NodeB .
  • NodeB ->sig is not 0 (it's NodeC ), the if is not met.
  • You call reverse with NodeB ->sig which is NodeC .
  • NodeC ->sig is 0 the if is met.
  • Return NodeC .
  • The value returned by the previous call is discarded (not picked up).
  • It is pointed to the next of NodeB (which is NULL ) to NodeB .
  • Point to the following from NodeB (which is NodeC ) to NULL .
  • Ends the function without returning anything.
  • The value returned by the previous call is discarded (not picked up).
  • Point to the next following of NodeA (which is NULL ) to NodeA .
  • Point to the following from NodeA (which is NodeB ) to NULL .
  • Ends the function without returning anything.
  • That nothing that you have returned, which could be anything 1 , is stored in l .
  • You call the print function with whatever l contains.

After calling reverse your nodes will be structured like this:

Suggestions.

You should correct the error in reverse by returning a value in all execution paths.

You should not mix concepts, a Node and a List are not the same, create a List class that contains Nodes, do not treat the Nodes as if they were a 2 list. The functions that you already have created ( inert , print and reverse ) would belong to the class List and the nodes would be private data of the same.

.

1 It could be a valid pointer, an invalid pointer, the first parameter passed to the function, the keys to enter the Pentagon or a random memory address.

2 It's as inadequate as saying that a Beja is a Car, although Cars have Bugs, Bugs will never be Cars.

    
answered by 02.02.2017 в 09:12