Reverter uma lista vinculada

Como reverter uma lista vinculada no C ++ é mostrada neste tutorial Linuxhint. Quando você reverte uma lista vinculada, o caminho do link é revertido e a cabeça se torna a cauda, ​​e a cauda se torna a cabeça. Ao trocar as posições dos nós, podemos entender isso rapidamente. Nesta troca, apenas mudamos as posições dos nós da esquerda para a direita ou vice-versa.

Lista vinculada: Esta é uma lista vinculada que queremos reverter.

Após a lista vinculada reversa: O abaixo será o resultado depois de reverter a lista acima ligada.

No diagrama de exemplo acima, podemos ver que o nó da cabeça e o nó da cauda mudam suas posições quando revertemos a lista vinculada. O nó da cabeça, que agora é um nó da cauda, ​​aponta para o nó nulo porque agora é um nó da cauda.

Etapas do algoritmo

1. Criamos um método principal e declaramos algumas variáveis ​​necessárias.
2. Então, nosso próximo passo é criar um método que possa criar uma lista vinculada. Este método nos ajuda a criar uma lista vinculada.
3. O próximo passo é criar um método para reverter a lista vinculada. Neste método, passamos por toda a lista vinculada e esse método reverterá a lista vinculada.
4. Agora, precisamos de outro método para exibir nosso resultado depois de revertê -lo.
5. Vamos combinar todos esses métodos acima em nosso método principal.

Vamos explicar a lista vinculada invertida usando algum formulário pictórico para facilitar o entendimento. Então, vamos começar com o exemplo.

Abaixo é uma lista vinculada que queremos reverter.

Passo 1. O nó de cor verde é um nó da cabeça, que aponta para o primeiro nó na startup.

Passo 2. Na próxima etapa, atravessaremos toda a lista vinculada até que não obteremos o ponteiro nulo ao lado do nó do cabeçalho. Para isso, vamos atribuir ao próximo nó um nome temporário, como mostrado no diagrama abaixo.

etapa 3. Como temos um novo nó de referência chamado "temporário", que pode nos ajudar a atravessar toda a lista vinculada até que não obtenhamos o ponteiro nulo, para que possamos definir o próximo link do nó do cabeçalho como nulo, o que não afetará o vinculado 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 nos mudamos para o próximo nó. Também mudamos o nó anterior de Null para apenas o nó anterior do nó atual. Então 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, como mostrado no diagrama abaixo.

Então, seguimos as mesmas etapas e, finalmente, teremos uma lista vinculada invertida.

Etapa 5.

Etapa 6.

Etapa 7.

Etapa 8.

Etapa 9.

Etapa 10.

Etapa 11.

Etapa 12.

Etapa 13.

Etapa 14. Nesta etapa, nossa lista vinculada reverteu.

Programa C ++ para reverter uma lista vinculada

#incluir
usando namespace std;
// método para criar o nó
Nó da estrutura
int valor;
Nó *NextNodePtr;
*nodeObject;
Void CreateLinkedList (int n);
vazio reverselinkedlist (node ​​** nodeObject);
Void Display ();
int main ()
int n, valor, item;
cout<<"How many nodes you want to create =>: ";
CIN >> n;
CreateLinkedList (n);
cout<<"\nInformation in the linked list: \n";
mostrar();
cout<<"\nLinked list after reversed\n";
reverselinkedlist (& nodeObject);
mostrar();
retornar 0;

// Este método criará a lista vinculada
Void CreateLinkedList (int n)
Nó da estrutura *FrontNode, *tempnode;
int valor, i;
nodeObject = (nó da estrutura *) Malloc (sizeof (nó da estrutura));
if (nodeObject == NULL)
cout<<" Not enough to assing memory";
outro
cout<<"Please enter the info of node 1 (number only): ";
CIN >> valor;
nodeObject-> value = value;
nodeObject-> nextNodePtr = null;
tempnode = nodeObject;
para (i = 2; i<=n; i++)
FrontNode = (Nó da estrutura *) Malloc (sizeof (nó da estrutura));
// quando nenhum nó na lista vinculada
if (frontNode == null)
cout<<"Memory can not be allocated";
quebrar;

outro
cout<<"Please enter the info of node "<CIN >> valor;
FrontNode-> value = value;
FrontNode-> nextNodePtr = null;
tempnode-> nextNodePtr = FrontNode;
tempnode = tempnode-> nextNodePtr;




Void ReverselinkedList (nó ** NodeObject)
Nó da estrutura *tempnode = null;
Nó da estrutura *anteriorNode = null;
Nó da estrutura *currentNode = ( *nodeObject);
while (CurrentNode != Null)
tempnode = currentNode-> nextNodePtr;
currentNode-> nextNodePtr = anteriorNode;
anteriornode = currentNode;
currentNode = tempnode;

(*nodeObject) = anteriorNode;

Void Display ()
Nó da estrutura *tempnode;
if (nodeObject == null)
cout<<"Linkedlist is empty";

outro
tempnode = nodeObject;
enquanto (tempnode != Nulo)

cout<valor<<"\t";
tempnode = tempnode-> nextNodePtr;


cout <

Saída

Quantos nós você deseja criar =>: 6
Por 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 vinculada:
101 95 61 19 12 11
Lista vinculada após revertida
11 12 19 61 95 101

Conclusão

Este artigo do Linuxhint revisou como reverter uma lista vinculada em C++. Existem outros métodos para reverter uma lista vinculada, mas esse é um método muito comum para reverter uma lista vinculada. Cabe a você decidir como você deseja resolver seus problemas, mas geralmente a função de lista vinculada reversa deve ser um loop simples com swaps de ponteiro.