Invert Simple List

Question

EXERCISE: Write a method that inverts a linked list:
Entree: 10, 99, 101, 666
Expected Result: 666, 101, 99, 10

I thought to follow the following logic:
It would arrive until the last element (666) with p and in the penultimate with q (101), it would have the p.Prox indicate until the q (that is, reversing these two, making the 666 - new head - indicate for the 101). Ai, in a loop, would make him repeat this process only going to the anteantepenultimate (99) and to the antepenultimate (10), reversing them too, until reaching the end. However, something is going wrong and I can’t find what. Someone can help me?

class E4 {

    ListaSimples e4 = new ListaSimples();
    public void inverterLista () {
        e4.insere(10);
        e4.insere(99);
        e4.insere(101);
        e4.insere(666);
        int nElementos = 4;
        int n;
        int k = nElementos;

        for (int i=0; i<nElementos; i++) {
            n = 1;
            No p = e4.cabeca;
            No q = e4.cabeca;

            // nessa parte faz com que ele chegue ate o numero e na
            // proxima vez, ate um numero menor e assim vai
            while (n<k) {
                q = p;
                p = p.prox;
                n++;
            }
            p.prox = q;
            k--;
        }

        for (int m=0; m<nElementos; m++){
            No imprimir = e4.cabeca;
            System.out.print(imprimir.letra+" ");
            imprimir = imprimir.prox;
        }

    }

    public static void main(String[] args) {
        E4 e4 = new E4 ();
        e4.inverterLista();
    }

}

Answer 1

There are several alternatives to this inversion. Keep in mind that you cannot lose the next element of the list, you should always keep a reference to it.

I like the recursive alternative to this question, but this is a very simple recursion, so I’m going to show you its iterative equivalent.

Recursive version

A simply linked list inversion is the process of doing the following:

ancestral -> atual -> descendente
// magia da inversão 
ancestral <- atual <- descendente

Basically consists of two steps:

1. Makes the current point to the ancestor
2. Do the downward flip

The order of the steps is irrelevant as long as the value of the atual and of descendente. So I’m going to create a method inverte who will receive a hypothetical ancestral and a atual. Note that the first element of the list has no ancestor, so I can call it null (or it can be a guardian element, whatever). As I have no guarantee that the last element on the list points to the null value, I will also pass the position of the current element and the amount of elements on the list.

Strategy to be followed:

1. If I’m not at the end (posAtual < tamanho), I do steps 2 and 3
2. I call reverse with the element atual.prox in the argument to atual, atual in the argument ancestral and posAtual + 1 in the argument to posAtual
3. atual.prox = ancestral

Note that if I save the value of atual.prox in the variable descendente, i can reverse steps 2 and 3. In Java, I’ll call recursion this way:

No novaCabeca = inverte(null, e4.cabeca, 0, nElementos);
e4.cabeca = novaCabeca; // para manter a cabeça válida 

I am particularly in favour of having an element counter within ListaSimples, or to have assurance that the last element points to null or to a guardian element.

Recursion is implemented like this:

public static No inverter(No ancestral, No atual, int posAtual, int nElementos) {
    // passo 1: se for além do tamanho da lista, não processa nada
    if (posAtual >= nElementos) {
        return ancestral; // último nó válido
    }
    // passo 2: inverter a lista descendente
    No fimLista = inverter(atual, atual.prox, posAtual + 1, nElementos);
    // passo 3: inverter o nó atual
    atual.prox = ancestral;

    return fimLista;
}

Out of curiosity, this one was a head recursion, because the recursive step is in the beginning. The memory required to make this recursion is o(nElementos), running time is also o(nElementos).

Turning into an iteration

I will turn this function first into a tail recursion, then remove the recursive step and make it fully iterative.

To turn into tail recursion, just reverse steps 2 and 3. As stated above, only one variable is needed to do this:

public static No inverter(No ancestral, No atual, int posAtual, int nElementos) {
    // passo 1: se for além do tamanho da lista, não processa nada
    if (posAtual >= nElementos) {
        return ancestral; // último elemento válido
    }
    // reservando o valor do próximo 
    No prox = atual.prox;
    // passo 3: inverter o nó atual
    atual.prox = ancestral;
    // passo 2: inverter a lista descendente
    return inverter(atual, prox, posAtual + 1, nElementos);
}

Note that posAtual is serving as iteration index, so we can exchange all this for a for, where the stop condition is the stop condition of the end of the recursion:

public static void inverterIterativo(ListaSimples l, int nElementos) {
    // simulando primeira chamada recursiva, note que os valores são os mesmos
    No ancestral = null;
    No atual = l.cabeca;
    for (int posAtual = 0; posAtual < nElementos; posAtual++) {
        No prox = atual.prox; // guarda o descendente para inverter no próximo passo
        atual.prox = ancestral; // inverte o atual

        // quando da chamada iterativa, atual é chamado com o valor de prox e ancestral com o valor de atual

        ancestral = atual;
        atual = prox;
    }

    // note que o último elemento válido ficou armazenado na variável ancestral
    l.cabeca = ancestral;
}

Note that this method now uses constant additional memory o(1), as opposed to the additional recursion memory that is o(nElementos). Time, however, continues in the same asymptotic behavior of o(nElementos).

Other alternatives?

At the moment, I think as another alternative to write in a size vector nElementos and copy back to the list nodes. Here we have an inversion of values, not addresses. As you are doing an exercise, I believe this will be the alternative that would give less points to you, but still doing the inversion (and I find a valid curiosity).

Note that it will be necessary to scroll through the list twice now, and that additional memory of o(nElementos).

public static void inverterIterativo(ListaSimples l, int nElementos) {
    int[] valores = new int[nElementos];
    // primeira iteração: povoa o vetor
    for (int i = 0, No atual = l.cabeca; i < nElementos; i++, atual = atual.prox) {
        valores[i] = atual.letra;
    }
    // segunda iteração: transmite os valores do vetor para os nós
    for (int i = nElementos - 1, No atual = l.cabeca; i >= 0; i--, atual = atual.prox) {
        atual.letra = valores[i]; // posição de i varia de traz para frente
    }
}

Answer 2

I don’t know if I understood the doubt right, but to reverse the positions, you can do so:

1) Create a counter in the class and increment it within the method insere class ListaSimples:

public void insere(int numero) {
    // INSTRUÇÕES PARA ADICIONAR NA LISTA
    cont++;
}

2) Make a loop that decreases the value of the variable cont:

int j = 0;

for (int i = cont; i > 0; i--) {
    numerosAoContrario[j] = numerosInformados[i];
    j++;
}

The variable i will receive the amount of numbers informed by the method insere and the loop will decrease from one to one the value until it reaches zero (this means that you are accessing the values backwards).

Already the variable j, will be instantiated outside the loop and incremented within it, so numerosAoContrario[0] = numerosInformados[4] (as in your example).