Inversão de uma lista encadeada simples

ron_lima
(usa Slackware)

Enviado em 13/03/2009 - 10:19h

Com o fim de iniciar uma discussão sobre algoritmos, pensei em um tópico interessante para tal. Este é um problema de praticidade rara, mas de resolução muito interessante. Seja uma lista encadeada simples de tal maneira que você tenha, em mãos, somente o primeiro elemento. Por ser uma lista encadeada simples, pode-se percorrê-la somente em um único sentido, ou seja, do primeiro ao último elemento:

e1 -> e2 -> e3 -> e4

Considerando-se que e1 é o primeiro elemento, e sendo esse o elemento que você tenha em mãos, como você escreveria um algoritmo para inverter essa lista de tal maneira que após a transformação o resultado seria:

e4 -> e3 -> e2 -> e1

Vamos ao debate, pessoal!

clovesjr
(usa Slackware)

Enviado em 13/03/2009 - 11:04h

A lista já existe em um bd ou é feito a entrada dos dados um a um?

ron_lima
(usa Slackware)

Enviado em 13/03/2009 - 13:50h

A lista lhe é entregue totalmente montada. O que você tem em mãos é somente o primeiro elemento da lista. A discussão é como, à partir do primeiro elemento, inverter a lista, conforme a descrição.

Lembre-se que estamos tratando de algoritmos. Portanto, banco de dados é irrelevante para este problema. Da mesma forma, implementações em linguagens de programação também são irrelevantes.

A premissa para este problema é que a lista lhe é entregue totalmente construída. As invariantes são as esperadas em uma lista encadeada simples, ou seja, o elemento corrente aponta para o próximo elemento de tal maneira que o próximo elemento não consegue apontar para o elemento corrente.

Note que não falei em ponteiros por que estes também são irrelevantes para a discussão, visto que estamos tratando de um algoritmo.