Odwróć powiązaną listę

Jak odwrócić połączoną listę w C ++ jest pokazany w tym samouczku Linuxhint. Po odwróceniu połączonej listy ścieżka łącza jest odwrócona, a głowa staje się ogonem, a ogon staje się głową. Wymieniając pozycje węzłów, możemy to szybko zrozumieć. W tym zamianie po prostu zmieniamy pozycje węzłów od lewej do prawej lub odwrotnie.

połączona lista: To jest linkowa lista, którą chcemy odwrócić.

Po odwróconej listy powiązanej: Poniższe będzie wynikiem po odwróceniu wyżej pominowanej listy.

Na powyższym przykładowym schemacie widzimy, że węzeł głowy i węzeł ogonowy zmieniają swoje pozycje, gdy odwracamy lista połączona. Węzeł głowy, który jest teraz węzłem ogonowym, wskazuje na węzeł zerowy, ponieważ jest teraz węzłem ogonowym.

Kroki algorytmu

1. Tworzymy główną metodę i deklarujemy niektóre wymagane zmienne.
2. Następnie naszym następnym krokiem jest utworzenie metody, która może utworzyć powiązaną listę. Ta metoda pomaga nam utworzyć powiązaną listę.
3. Następnym krokiem jest utworzenie metody odwrócenia listy połączonej. W tej metodzie przekazujemy całą listę połączoną, a ta metoda odwróci linkę.
4. Teraz potrzebujemy innej metody, aby wyświetlić nasz wynik po odwróceniu.
5. Połączymy wszystkie powyższe metody z naszą główną metodą.

Wyjaśnimy odwróconą listę połączoną za pomocą formularza obrazowego, aby ułatwić zrozumienie. Zacznijmy więc od przykładu.

Poniższa jest połączona lista, którą chcemy odwrócić.

Krok 1. Zielony węzeł to węzeł główny, który wskazuje na pierwszy węzeł w startupu.

Krok 2. W następnym kroku przemierzamy całą listę połączoną, dopóki nie otrzymamy wskaźnika zerowego obok węzła nagłówka. W tym celu przypiszmy następny węzeł tymczasową nazwę, jak pokazano na poniższym schemacie.

Krok 3. Ponieważ mamy nowy węzeł odniesienia o nazwie „Tymczasowy”, który może pomóc nam przemierzać całą listę połączoną, dopóki nie otrzymamy wskaźnika zerowego, abyśmy mogli ustawić następny link węzła nagłówka jako null, co nie wpłynie na połączone Lista, jak pokazano poniżej na schemacie. Wskaźnik zerowy obok bieżącego węzła nazywany jest poprzednim węzłem.

Krok 4. Teraz przenosimy tymczasowy węzeł do następnego węzła i bieżący węzeł do poprzedniego węzła tymczasowego. Więc teraz przeprowadziliśmy się do następnego węzła. Zmieniamy również poprzedni węzeł z null na poprzedni węzeł bieżącego węzła. Więc teraz tymczasowy węzeł zajmie się wszystkimi traversami do wskaźnika zerowego, abyśmy mogli ustawić link bieżącego węzła do poprzedniego węzła, a teraz wskazuje na poprzedni węzeł, jak pokazano na poniższym schemacie.

Dlatego wykonujemy te same kroki i w końcu otrzymamy odwróconą listę połączoną.

Krok 5.

Krok 6.

Krok 7.

Krok 8.

Krok 9.

Krok 10.

Krok 11.

Krok 12.

Krok 13.

Krok 14. Na tym etapie nasza lista powiązana odwróciła.

Program C ++, aby odwrócić powiązaną listę

#włączać
za pomocą przestrzeni nazw Std;
// metoda utworzenia węzła
Node struct
wartość int;
Węzeł *NextNodeptr;
*nodeObject;
void createLinkedList (int n);
void reverselinkedList (węzeł ** nodeObject);
void display ();
int main ()
int n, wartość, pozycja;
Cout<<"How many nodes you want to create =>: ";
cin >> n;
CreateLinkedList (n);
Cout<<"\nInformation in the linked list: \n";
wyświetlacz();
Cout<<"\nLinked list after reversed\n";
reverselinkedList (& nodeObject);
wyświetlacz();
powrót 0;

// Ta metoda utworzy linkowaną listę
void createLinkedList (int n)
Node struct *frontNode, *tempnode;
wartość int, i;
nodeObject = (struct node *) malloc (sizeof (struct node));
if (nodeObject == null)
Cout<<" Not enough to assing memory";
w przeciwnym razie
Cout<<"Please enter the info of node 1 (number only): ";
CIN >> Wartość;
nodeObject-> wartość = wartość;
nodeObject-> NextNodeptr = null;
tempNode = nodeObject;
dla (i = 2; i<=n; i++)
frontNode = (struct node *) malloc (sizeof (node ​​struct));
// Gdy żaden węzeł nie ma na listy powiązanej
if (frontNode == null)
Cout<<"Memory can not be allocated";
przerwa;

w przeciwnym razie
Cout<<"Please enter the info of node "<CIN >> Wartość;
frontNode-> wartość = wartość;
frontNode-> NextNodeptr = null;
tempNode-> NextNodeptr = frontNode;
tempnode = tempNode-> NextNodeptr;




void reverselinkedList (węzeł ** nodeObject)
struct node *tempnode = null;
struct node *poprzedniNode = null;
struct node *currentNode = ( *nodeObject);
While (CurrentNode != Null)
tempNode = currentNode-> NextNodeptr;
currentNode-> NextNodeptr = poprzedniNode;
poprzedniNode = currentNode;
currentNode = tempnode;

(*nodeObject) = poprzedniNode;

void display ()
node struct *tempnode;
if (nodeObject == null)
Cout<<"Linkedlist is empty";

w przeciwnym razie
tempNode = nodeObject;
While (tempnode != Null)

Cout<wartość<<"\t";
tempnode = tempNode-> NextNodeptr;


Cout <

Wyjście

Ile węzłów chcesz utworzyć =>: 6
Wprowadź informacje o węźle 1 (tylko numer): 101
Wprowadź informacje o węźle 2: 95
Wprowadź informacje o węźle 3: 61
Wprowadź informacje o węźle 4: 19
Wprowadź informacje o węźle 5: 12
Wprowadź informacje o węźle 6: 11
Informacje na połączonej liście:
101 95 61 19 12 11
Połączona lista po odwróceniu
11 12 19 61 95 101

Wniosek

Ten artykuł z Linuxhint dokonał przeglądu sposobu odwrócenia połączonej listy w C++. Istnieją kilka innych metod odwrócenia połączonej listy, ale jest to bardzo powszechna metoda odwrócenia połączonej listy. Od Ciebie zależy, w jaki sposób chcesz rozwiązać swoje problemy, ale ogólnie funkcja listy odwrotnej powinna być prostą pętlą z wymianami wskaźników.