¿Es posible revertir una lista vinculada que contiene un ciclo?

Question

Estoy viendo algunas preguntas de la entrevista, y una de ellas pide revertir una lista vinculada que contiene un ciclo. Así que supongo que tenía una lista enlazada como la siguiente:

  F <- E 
      | /\ 
      V | 
A -> B -> C -> D 

A continuación, la inversión de la lista sería crear lo siguiente:

  F -> E 
     /\ | 
      | V 
A <- B <- C <- D 

El problema aquí es que hay un conflicto entre el que los nodos C debe estar apuntando al . Entonces, ¿eliminaríamos el vínculo entre C y F?

Answer 1

Matemáticamente, puede pensar en una lista enlazada (posiblemente conteniendo un ciclo) como una función parcial de un conjunto de nodos en sí mismo, donde cada nodo mapea a su sucesor y cada nodo es eventualmente accesible desde el nodo de inicio. (El último nodo no tiene sucesor). Invertir una lista enlazada implicaría invertir esta función, ya que seguir un enlace y luego retroceder debería terminar en el punto donde comenzó.

Si la lista vinculada no contiene un ciclo, esta función parcial es inyectiva (uno a uno), lo que significa que no hay dos nodos asignados al mismo sucesor. Las funciones de inyección se pueden invertir, por lo que puede invertir una lista vinculada regular. Sin embargo, si la lista contiene un ciclo, entonces hay dos nodos con el mismo sucesor, por lo que la función no es inyectiva y, por lo tanto, no tiene una inversa. Entonces, no, no puede revertir la lista vinculada y esperar obtener otra lista vinculada, si la lista tiene un ciclo.

Sin embargo, si trata la lista vinculada como un gráfico más general en el que cada nodo puede tener cualquier número de bordes entrantes o salientes, entonces el inverso sí existe. Ya no es una lista vinculada.

Answer 2

La lista original sería AB CDEF CDEF CDEF ... Para invertir que se necesitaría una lista enlazada que genera FEDC un número infinito de veces seguido de BA, así que diría que no, no hay manera de construir una lista enlazada que generaría esa secuencia.