Omvendt en koblet liste

Hvordan reversere en koblet liste i C ++ vises i denne Linuxhint -opplæringen. Når du reverserer en koblet liste, blir koblingsstien reversert, og hodet blir halen, og halen blir hodet. Ved å bytte posisjonene til nodene, kan vi forstå dette raskt. I denne byttet endrer vi bare posisjonene til nodene fra venstre til høyre eller omvendt.

koblet liste: Dette er en lenket liste som vi ønsker å snu.

Etter omvendt lenket liste: Nedenfor blir resultatet etter å ha reversert listen ovenfor.

I eksemplet ovenfor kan vi se at hodeknuten og haleknuten endrer posisjonene sine når vi reverserer den koblede listen. Hodeknuten, som nå er en haleknute, peker på nullnoden fordi den nå er en haleknute.

Algoritme trinn

1. Vi lager en hovedmetode og erklærer noen nødvendige variabler.
2. Deretter er vårt neste trinn å lage en metode som kan lage en koblet liste. Denne metoden hjelper oss å lage en lenket liste.
3. Neste trinn er å lage en metode for å reversere den koblede listen. I denne metoden passerer vi hele den koblede listen, og denne metoden vil reversere den koblede listen.
4. Nå trenger vi en annen metode for å vise resultatet vårt etter å ha reversert det.
5. Vi vil kombinere alle disse metodene ovenfor til hovedmetoden vår.

Vi kommer til å forklare omvendt lenket liste ved hjelp av en eller annen billedform for å gjøre det lettere å forstå. Så la oss starte med eksemplet.

Nedenfor er en koblet liste som vi ønsker å snu.

Trinn 1. Den grønnfargede noden er en hodeknute, som peker på den første noden i oppstarten.

Steg 2. I neste trinn vil vi krysse hele koblede listen til vi ikke får NULL -pekeren ved siden av overskriftsnoden. For det skal vi tilordne neste node et midlertidig navn, som vist i diagrammet nedenfor.

Trinn 3. Ettersom vi har en ny referanseknute som heter "Midlertidig", som kan hjelpe oss med å krysse hele lenket listen før vi ikke får nullpekeren, så kan vi angi neste lenke til toppnoden som null, noe som ikke vil påvirke den koblede Liste som vist nedenfor i diagrammet. NULL -pekeren ved siden av den gjeldende noden kalles forrige node.

Trinn 4. Nå flytter vi den midlertidige noden til neste node og gjeldende node til den forrige midlertidige noden. Så nå har vi flyttet til neste node. Vi endrer også den forrige noden fra null til bare den forrige noden til den nåværende noden. Så nå vil den midlertidige noden ta seg av alle traverses til NULL -pekeren slik at vi kan stille inn lenken til den gjeldende noden til den forrige noden, og nå peker den til den forrige noden, som vist i nedenfor diagrammet.

Så vi følger de samme trinnene, og til slutt vil vi få en omvendt koblet liste.

Trinn 5.

Trinn 6.

Trinn 7.

Trinn 8.

Trinn 9.

Trinn 10.

Trinn 11.

Trinn 12.

Trinn 13.

Trinn 14. På dette trinnet reverserte vår koblede liste.

C ++ -program for å reversere en koblet liste

#inkludere
ved hjelp av navneområdet STD;
// Metode for å lage noden
struct node
int verdi;
Node *NextNodeptr;
*NodeObject;
void createLinkedList (int n);
void ReverSelinkedList (Node ** NodeObject);
void display ();
int main ()
int n, verdi, vare;
cout<<"How many nodes you want to create =>: ";
cin >> n;
CreateLinkedList (N);
cout<<"\nInformation in the linked list: \n";
vise();
cout<<"\nLinked list after reversed\n";
reverselinkedlist (& nodeObject);
vise();
retur 0;

// denne metoden vil opprette den koblede listen
void createLinkedList (int n)
struct node *frontnode, *tempnode;
int verdi, i;
nodeObject = (struct node *) malloc (sizeof (struct node));
if (nodeObject == null)
cout<<" Not enough to assing memory";
annet
cout<<"Please enter the info of node 1 (number only): ";
cin >> verdi;
NodeObject-> Verdi = verdi;
nodeObject-> nextNodeptr = null;
tempNode = nodeObject;
for (i = 2; i<=n; i++)
frontnode = (struct node *) malloc (sizeof (struct node)));
// når ingen node i den koblede listen
if (frontnode == null)
cout<<"Memory can not be allocated";
gå i stykker;

annet
cout<<"Please enter the info of node "<cin >> verdi;
frontnode-> verdi = verdi;
frontnode-> nextNodeptr = null;
tempnode-> nextNodeptr = frontnode;
tempNode = tempnode-> nextNodeptr;




void reverselinkedlist (node ​​** nodeObject)
struct node *tempnode = null;
struct node *forrige node = null;
struct node *currentNode = ( *nodeObject);
mens (CurrentNode != Null)
tempNode = currentNode-> nextNodeptr;
currentNode-> nextNodeptr = forrige node;
ForrigeNode = CurrentNode;
currentNode = tempnode;

(*NodeObject) = forrige node;

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

annet
tempNode = nodeObject;
mens (tempnode != Null)

cout<verdi<<"\t";
tempNode = tempnode-> nextNodeptr;


cout <

Produksjon

Hvor mange noder vil du opprette =>: 6
Vennligst skriv inn informasjonen til node 1 (bare nummer): 101
Vennligst skriv inn informasjonen i Node 2: 95
Vennligst skriv inn informasjonen i Node 3: 61
Vennligst skriv inn informasjonen i Node 4: 19
Vennligst skriv inn informasjonen i noden 5: 12
Vennligst skriv inn informasjonen i noden 6: 11
Informasjon i den koblede listen:
101 95 61 19 12 11
Koblet liste etter reversert
11 12 19 61 95 101

Konklusjon

Denne Linuxhint -artikkelen har gjennomgått hvordan du kan snu en koblet liste i C++. Det er noen andre metoder for å reversere en koblet liste, men dette er en veldig vanlig metode for å snu en koblet liste. Det er opp til deg å bestemme hvordan du vil løse problemene dine, men generelt bør den omvendte koblede listefunksjonen være en enkel sløyfe med pekerbytter.