lista encadeada: Esta é uma lista encadeada que queremos reverter.
Depois da lista encadeada invertida: O abaixo será o resultado depois de inverter a lista acima.
No diagrama de exemplo acima, podemos ver que o nó principal e o nó final mudam de posição quando invertemos a lista encadeada. O nó principal, que agora é um nó final, aponta para o nó nulo porque agora é um nó final.
Passos do Algoritmo
- Criamos um método principal e declaramos algumas variáveis necessárias.
- Então, nosso próximo passo é criar um método que possa criar uma lista encadeada. Este método nos ajuda a criar uma lista encadeada.
- A próxima etapa é criar um método para inverter a lista encadeada. Nesse método, passamos toda a lista encadeada e esse método inverterá a lista encadeada.
- Agora, precisamos de outro método para exibir nosso resultado após invertê-lo.
- Combinaremos todos esses métodos acima em nosso método principal.
Vamos explicar a lista encadeada invertida usando alguma forma pictórica para torná-la mais fácil de entender. Então vamos começar com o exemplo.
Abaixo está uma lista encadeada que queremos reverter.
Passo 1 . O nó verde é um nó principal, que aponta para o primeiro nó na inicialização.
Passo 2. Na próxima etapa, percorreremos toda a lista encadeada até não obtermos o ponteiro nulo próximo ao nó do cabeçalho. Para isso, vamos atribuir ao próximo nó um nome temporário, conforme mostrado no diagrama abaixo.
Etapa 3. Como temos um novo nó de referência chamado “temporário”, que pode nos ajudar a percorrer toda a lista vinculada até não obtermos o ponteiro nulo, podemos definir o próximo link do nó de cabeçalho como nulo, o que não afetará o vinculado lista como mostrado abaixo no diagrama. O ponteiro nulo ao lado do nó atual é chamado de nó anterior.
Passo 4. Agora, movemos o nó temporário para o próximo nó e o nó atual para o nó temporário anterior. Então agora passamos para o próximo nó. Também alteramos o nó anterior de nulo para apenas o nó anterior do nó atual. Portanto, agora o nó temporário cuidará de todas as travessias até o ponteiro nulo para que possamos definir o link do nó atual para o nó anterior, e agora está apontando para o nó anterior, conforme mostrado no diagrama abaixo.
Assim, seguimos os mesmos passos e, por fim, obteremos uma lista encadeada invertida.
Passo 5 .
Passo 6.
Passo 7.
Passo 8.
Passo 9.
Passo 10.
Passo 11.
Passo 12.
Passo 13.
Passo 14. Nesta etapa, nossa lista vinculada foi invertida.
Programa em C++ para inverter uma lista encadeada
#includeusando namespace std ;
// Método para criar o nó
estrutura nó {
int valor ;
nó * nextNodePtr ;
} * nodeObject ;
vazio criarLinkedList ( int n ) ;
vazio reverseLinkedList ( nó ** nodeObject ) ;
vazio exibição ( ) ;
int a Principal ( ) {
int n,valor,item ;
cout << 'Quantos nós você deseja criar =>: ' ;
comendo >> n ;
criarLinkedList ( n ) ;
cout << ' \n Informações na lista encadeada: \n ' ;
exibição ( ) ;
cout << ' \n Lista encadeada depois de invertida \n ' ;
reverseLinkedList ( & nodeObject ) ;
exibição ( ) ;
Retorna 0 ;
}
// Este método irá criar a lista encadeada
vazio criarLinkedList ( int n ) {
estrutura nó * frontNode, * tempNode ;
int valor, eu ;
nodeObject = ( estrutura nó * ) malloc ( tamanho de ( estrutura nó ) ) ;
E se ( nodeObject == NULO )
cout << 'Não é suficiente para avaliar a memória' ;
senão {
cout << 'Por favor, insira as informações do nó 1 (somente número): ' ;
comendo >> valor ;
nodeObject - > valor = valor ;
nodeObject - > nextNodePtr = NULO ;
tempNode = nodeObject ;
por ( eu = dois ; eu <= n ; eu ++ ) {
frontNode = ( estrutura nó * ) malloc ( tamanho de ( estrutura nó ) ) ;
// Quando não há nenhum nó na lista encadeada
E se ( frontNode == NULO ) {
cout << 'Memória não pode ser alocada' ;
parar ;
}
senão {
cout << 'Por favor, insira as informações do nó' << eu << ':' ;
comendo >> valor ;
frontNode - > valor = valor ;
frontNode - > nextNodePtr = NULO ;
tempNode - > nextNodePtr = frontNode ;
tempNode = tempNode - > nextNodePtr ;
}
}
}
}
vazio reverseLinkedList ( nó ** nodeObject ) {
estrutura nó * tempNode = NULO ;
estrutura nó * Nó anterior = NULO ;
estrutura nó * currentNode = ( * nodeObject ) ;
enquanto ( currentNode ! = NULO ) {
tempNode = currentNode - > nextNodePtr ;
currentNode - > nextNodePtr = Nó anterior ;
Nó anterior = currentNode ;
currentNode = tempNode ;
}
( * nodeObject ) = Nó anterior ;
}
vazio exibição ( ) {
estrutura nó * tempNode ;
E se ( nodeObject == NULO ) {
cout << 'Lista vinculada está vazia' ;
}
senão {
tempNode = nodeObject ;
enquanto ( tempNode ! = NULO )
{
cout << tempNode - > valor << ' \t ' ;
tempNode = tempNode - > nextNodePtr ;
}
}
cout << fim ;
}
Resultado
Quantos nós você deseja criar =>: 6Por favor, insira as informações do nó 1 (somente número): 101
Por favor, insira as informações do nó 2: 95
Por favor, insira as informações do nó 3: 61
Por favor, insira as informações do nó 4: 19
Por favor, insira as informações do nó 5: 12
Por favor, insira as informações do nó 6: 11
Informações na lista encadeada:
101 95 61 19 12 11
Lista encadeada depois de invertida
11 12 19 61 95 101
Conclusão
Este artigo do LinuxHint revisou como reverter uma lista encadeada em C++. Existem alguns outros métodos para inverter uma lista vinculada, mas este é um método muito comum para reverter uma lista vinculada. Cabe a você decidir como deseja resolver seus problemas, mas geralmente a função de lista encadeada reversa deve ser um loop simples com trocas de ponteiro.