[ Foro de Pascal ]

Invertir una lista enlazada simple.

03-Nov-2012 22:52
Luis Torres (+12)
9 Respuestas

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.


27-Nov-2012 14:08
Nacho Cabanes (+30)

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.


28-Nov-2012 00:18
Luis Torres (+12)

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


29-Nov-2012 22:26
Nacho Cabanes (+30)

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.


30-Nov-2012 02:14
Luis Torres (+12)

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.


05-Dec-2012 10:02
Nacho Cabanes (+30)

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.


06-Dec-2012 22:05
Luis Torres (+12)

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;


15-Dec-2012 11:21
Nacho Cabanes (+30)

¡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.


17-Dec-2012 21:20
Luis Torres (+12)

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


17-Dec-2012 23:30
Luis Torres (+12)

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;
 






(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)