hvordan man kan vende en enkelt linket liste

Indlæg af Birthe Møller     opdateret: 2012-02-02

Det er almindeligt at have behov for at vende en sammenkædet liste , men det kan være svært at gøre det ordentligt . En af de enkleste løsninger er at skifte gennem løkken , vende hver pointer . Denne pseudokode viser, hvordan du udfører denne proces , samtidig med at holde styr på de nødvendige variabler . Den pseudokode er generisk nok, at du skal være i stand til at tilpasse den til det sprog din kode er i.
1 .
Check for simple kant sager . Hvis hovedet markøren er Null , listen er tom , og intet arbejde der skal gøres . Hvis hovedet næste markøren er Null , er der kun ét element i listen , så får det modsatte gør ikke noget .
hvis head=null derefter vende tilbage
hvis hoved-> next=null derefter . afkast
2
Initialiser tre pointers : forrige , nuværende og næste år. " Forrige "og " nuværende " skal pege i spidsen knude på listen . "Næste " skal pege på det andet knudepunkt ved at se på markøren i hovedet knude
pointer forrige=hoved .
markøren nuværende=hoved ;
viseren næste=hoved-> næste .
3
Sæt hovedknudepunktet næste markøren til null . Hovedet node bliver den sidste node i listen , så der bliver ingen noder efter det.
head-> next=null
4 .
Loop gennem listen vende retningen af pegepinde . De tre pointers initialiseret tidligere er brugt til at holde styr på den aktuelle position på listen .
mens næste !=null //En null næste pointer betyder, at vi er nået til slutningen af listen
strøm=næste //Advance den nuværende markøren
næste=løbende > næste //Advance næste markøren
løbende > next=forrige //Point den aktuelle node til den forrige node , bakning linket
forrige=strøm //Før sidste markøren
ende mens
5 .
Punkt hovedet variabel på listen 's nye chef .
head=nuværende

gode råd og advarsler


  • Hvis du har brug for at skifte gennem en sammenkædet liste i begge retninger overveje at indføre en dobbelt-linket liste .


  • Previous:hvordan man beregner den dag i ugen for ethvert år Next:hvordan man åbner en postsættet



     

    Kommentarer

    Code:
    change