Invertir una lista enlazada

Una lista enlazada es un tipo especial de estructura de datos en la que un elemento determinado de la lista —llamado nodo— tiene uno o dos punteros a otros nodos de la lista. La lista enlazada puede ser:

• Enlazada simple: Cada nodo apunta únicamente al siguiente nodo de la lista, pero no de vuelta al nodo anterior.
• Doblemente enlazada: Cada nodo apunta tanto al siguiente nodo como al nodo anterior.

Por ejemplo, considera la lista enlazada simple representada por el arreglo [1, 2, 3, 4]

 1 --> 2--> 3 --> 4

Observa que desde el nodo 3, por ejemplo, puedes seguir su puntero hasta el nodo 4, pero no puedes ir desde el nodo 3 hasta el nodo 2!

 ... 2 <-x- 3

Como no existe un puntero del nodo 3 al nodo 2, el nodo 3 «desconoce» cuál es su nodo anterior (el nodo 2).

Invierte una lista enlazada.

Para obtener el premio del Desafío Súper Mega Increíble (no es real), también debes hacer lo siguiente:

1. Invierte la lista in situ. Para quienes saben de CS, eso significa usar O(1) de espacio auxiliar. Para quienes no, imagina que no tienes mucho espacio adicional para guardar otra «copia» de tu lista enlazada.

2. Usa un método de prototipo agregado a la clase LinkedList incluida. Si incluyes un método de prototipo, ten en cuenta que tendrá prioridad sobre cualquier método que no sea del prototipo.

Nota que no hacer estas cosas aún te permitirá superar el desafío: ¡solo te darán puntos extra de estilo!

Por último, ten en cuenta que DEBES devolver la lista enlazada invertida al final de la función (¡sin importar cómo lo hagas!).

Ejemplos

[1, 2, 3, 4] ➞ [4, 3, 2, 1]

[8, 6, 7, 5, 3, 0, 9] ➞ [9, 0, 3, 5, 7, 6, 8]

["a", "b", "c", "e"] ➞ ["e" ,"c", "b", "a"]

Consejos

• Tu lista enlazada inicial se creará con new LinkedList(arr), donde arr es una lista de elementos como [1,2,3,4].
• La lista enlazada tiene tres métodos auxiliares:
  • insertHead(v): Inserta un nodo nuevo con el valor v al principio de la lista.
  • insertTail(v): Inserta un nodo nuevo con el valor v al final de la lista.
  • print(): Recorre la lista (del principio al final), agrega cada valor a un arreglo y devuelve el arreglo.
• También tiene dos propiedades predeterminadas:
  • head: el nodo inicial actual de la lista. Su valor predeterminado es null.
  • tail: el nodo final predeterminado de la lista. Su valor predeterminado es null. Ten en cuenta que, si la lista tiene exactamente un nodo, tail será igual a head.
• En términos generales, si estás invirtiendo la lista in situ, tendrás que descubrir cómo «invertir» esos punteros unidireccionales.