[ Foro de Pascal ]

Invertir una lista enlazada simple.

Ante todo un gran saludo a esta comunidad, la razón que me trae aquí es porque tengo un problema que me pide invertir una lista enlazada simple apuntada por L. Necesito que por favor me den un algoritmo para hacerlo. La lista resultante debe ser la misma lista pero el último elemento debe ahora ser el primero, el penúltimo debe ahora ser el segundo y así con todos los nodos de la lista, el puntero L deberá apuntar ahora al que era el último elemento antes y ahora es el primer elemento. El algoritmo debe ser iterativo. Un abrazo a todos.

Perdona el retraso en contestar, he estado cerca de tres semanas sin entrar al foro. ¿Lo tienes resuelto ya? La idea es sencilla la lista que ya tienes la debes recorrer en orden (que es lo normal) y en la nueva lista debes ir insertando siempre al principio (como en una "pila"). No es un "insertar" habitual, pero debería resultarte fácil de hacer.

El problema es que no se permite utilizar una nueva lista, sino hacer todo el procedimiento en la misma lista. Saludos.

Eso no tiene por qué ser un problema. La "nueva lista" puede ser un dato intermedio, que usas como auxiliar. ¿O sólo te permiten usar un único nodo extra como dato auxiliar?  ¿O dos nodos?  Si no se especifica, debería ser razonable que puedas usar tantos datos auxiliares como tú consideres necesarios, y la forma más sencilla es usar una lista auxiliar, del mismo tamaño que la tuya.

No, profesor, el problema exige no se utilicen listas auxiliares, sino que todo se haga sobre la lista original.
Saludos y gracias por su respuesta.

Podemos intentarlo, pero en cualquier caso, para que la respuesta sea lo más concreta posible, lo ideal sería que pusieras tu implementación de la lista, para que partamos de ella, no desde cero.

Gracias por su respuesta y su tiempo. El enunciado dice así:
Construir un procedimiento que invierta una lista simple enlazada apuntada por L. La lista puede estar vacía. No se tiene que generar una nueva lista. El tipo de dato punt es
punt = ^elemento;
elemento = record
  dato: integer;
  sig: punt;
 end;

procedure invertir (var p: punt);
var
q,r: punt;
Begin
if p<>nil then
 begin
   r:= p;
   q:= p^.sig;
   p^.sig:= nil;

¡Pero si lo tienes ya casi completo!

Ese es el algoritmo clásico. Aquí lo tienes en C, junto con algunos comentarios de usuarios (en inglés):

http://stackoverflow.com/questions/1801549/reverse-a-singly-linked-list

como puedes ver, te falta poco más que cambiar el "if" por un "while", para que analice todos los nodos, y añadir "q^.sig := r;" como último paso del "while". También te falta cambiar la dirección del puntero inicial.

Muchas gracias por la respuesta. Era lo que estaba esperando. Saludos.

Muchas gracias. Ya llevé el algoritmo implícito en el código C a Pascal, lo probé y este es el resultado. Yo hice con los ojos vendados, no me resultó, luego hice una corrida de mesa y me dí cuenta de lo que faltaba. Lo probé y resultó de maravilla. Aquí dejo el código del procedimiento en Pascal:

procedure invertir(var p:Tiponodo);
var
 q,r: Tiponodo;
Begin
  q:= nil;
  { En cada ciclo las variables r,q y p guardan tres nodos, r el primero, q el segundo y }
  { p el tercero:                                                                        }
  { r apuntara a un nodo, q al nodo despues de r y, p al nodo siguiente despues de q.    }
  { Por lo tanto, para hacer los cambios en la lista, q^.sgte guardara la direccion de r }
  { en cada ciclo hasta que se recorra toda la lista.                                    }
  { Finalmente cuando p valga nil se termina el ciclo, pero q guardara la direccion del  }
  { ultimo nodo, por tanto haremos que p guarde la direccion de q. Con lo cual ya tenemos}
  { la lista invertida y, p apunta al primer nodo de esta lista invertida (ultimo nodo   }
  { de la lista original.                                                                }
  while (p<>nil) do
   begin
     r:= q;
	 q:= p;
	 p:= p^.sgte;
	 q^.sgte:= r;
   end;
  p:= q;
End;