Sortering av en länkad lista kan göras med olika algoritmer, ett vanligt tillvägagångssätt är att använda merge sort. Slå samman sortering följer en splittra och erövra-strategi:
1. Dela upp listan:
- Om listan innehåller en eller noll noder anses den redan sorterad.
- Annars delar du upp listan i två ungefär lika stora halvor.
2. Erövra (sortera underlistorna):
- Applicera rekursivt sammanslagningssorteringsalgoritmen på båda halvorna av listan och sortera dem effektivt.
3. Slå samman de sorterade underlistorna:
- Börja med två pekare, en pekar på huvudet på varje sorterad underlista.
- Jämför data i noderna som pekas av dessa pekare för att avgöra vilket element som kommer först i sorterad ordning.
- Lägg till det mindre elementet till en ny lista som konstrueras.
- Flytta motsvarande pekare till nästa nod i underlistan.
4. Upprepa steg 3:
- Fortsätt att jämföra och slå samman element från båda underlistorna, flytta pekare efter behov.
- Upprepa denna process tills alla element från båda underlistorna har slagits samman till den nya listan.
5. Återställ den sammanslagna sorterade listan:
- När alla element har slagits samman, representerar den resulterande nya listan den sorterade länkade listan. Returnera denna sorterade lista som det slutliga svaret.
Genom att systematiskt dela upp listan i mindre delar, sortera dem och slå samman dem igen, sorterar merge sort effektivt hela den länkade listan i stigande ordning. Tidskomplexiteten för detta tillvägagångssätt är O(n log n), där n är antalet noder i den länkade listan.
