Hvordan Reverse en enkeltlenket liste

Det er vanlig å trenge å reversere en lenket liste, men det kan være vanskelig å gjøre det riktig. En av de enkleste løsningene er å iterere gjennom løkken, vend hver pekeren. Denne pseudo viser hvordan du utfører denne prosessen mens du holder styr på de nødvendige variablene. Den pseudokode er generisk nok til at du bør være i stand til å tilpasse den til hva språkkoden din er i.

Bruksanvisning

1 Se etter enkle kant tilfeller. Hvis hodet pekeren er null, er listen tom og ingen jobb som må gjøres. Hvis hodet neste pekeren er null, er det bare ett element i listen, så reversere det gjør ingenting.

hvis hode = null deretter tilbake
hvis hode-> neste = null deretter retur

2 Initial tre pekere: forrige, nåværende og neste. \ "Forrige \" og \ "dagens \" skal peke på hovedknutepunktet av listen. \ "Neste \" skal peke på den andre noden ved å se på pekeren i hodet node.

pekeren prev = hode
GÅ
pekeren nåværende = hode
GÅ
markøren ved siden = hode-> neste;

3 Sett hodet node neste pekeren til null. Hovedknutepunktet vil bli den siste node i listen, så det blir ingen noder etter det.

hode-> neste = null

4 Sløyfe gjennom listen for å reversere retningen av pekere. De tre pekere initialisert tidligere er brukt til å holde styr på den aktuelle posisjonen i listen.

mens neste! = null // En null neste peker betyr at vi har kommet til slutten av listen
current = neste // Advance gjeldende peker
next = strømføren-> neste // Advance neste pekeren
strømføren-> next = prev // Rett gjeldende node til forrige node, reversere koblingen
prev = aktuell // Advance siste pekeren
slutten mens

5 Rett hodet variabel på listen sin nye leder.

hode = strøm

Hint

• Hvis du trenger å iterere gjennom en lenket liste i begge retninger vurdere å gjennomføre en dobbelt-lenket liste.