Inverter uma lista encadeada

Uma lista encadeada é um tipo especial de estrutura de dados em que um determinado item da lista — chamado nó — tem um ou dois ponteiros para outros nós da lista. A lista encadeada pode ser:

  • Encadeada simples: Cada nó aponta apenas para o próximo nó da lista, mas não de volta para o nó anterior.
  • Duplamente encadeada: Cada nó aponta tanto para o próximo nó quanto para o nó anterior.

Por exemplo, considere a lista encadeada simples representada pelo array [1, 2, 3, 4]

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

Observe que, a partir do nó 3, por exemplo, você pode seguir seu ponteiro até o nó 4, mas não pode voltar do nó 3 para o nó 2!

 ... 2 <-x- 3

Como não há um ponteiro do nó 3 para o nó 2, o nó 3 «desconhece» seu nó anterior (o nó 2).

Inverta uma lista encadeada.

Para ganhar o prêmio do Desafio Super Mega Incrível (não é sério), você também deve fazer o seguinte:

  1. Inverta a lista in-place. Para quem é da área de CS, isso significa usar O(1) de espaço auxiliar. Para quem não é, imagine que você não tenha muito espaço extra para armazenar outra «cópia» da sua lista encadeada.

  2. Use um método de protótipo adicionado à classe LinkedList incluída. Se você incluir um método de protótipo, observe que ele terá precedência sobre qualquer método que não seja de protótipo.

Observe que não fazer essas coisas ainda permitirá que você passe no desafio: elas só rendem pontos extras de estilo!

Por fim, observe que você DEVE retornar a lista encadeada invertida ao final da função (faça isso do jeito que quiser!).

Exemplos

[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"]

Dicas

  • Sua lista encadeada inicial será criada com new LinkedList(arr), em que arr é uma lista de itens como [1,2,3,4].
  • A lista encadeada tem três métodos auxiliares:
    • insertHead(v): Insere um novo nó com o valor v no início da lista.
    • insertTail(v): Insere um novo nó com o valor v no final da lista.
    • print(): Percorre a lista (do início ao fim), adiciona cada valor a um array e retorna o array.
  • Ela também tem duas propriedades padrão:
    • head: o nó inicial atual da lista. O valor padrão é null.
    • tail: o nó final padrão da lista. O valor padrão é null. Observe que, se a lista tiver exatamente um nó, tail será igual a head.
  • De modo geral, se você estiver invertendo a lista in-place, precisará descobrir uma forma de «inverter» esses ponteiros unidirecionais.