Sortowanie przez scalanie Mariusz: https://imgur.com/a/Evlsu0t https://imgur.com/a/CGMZfJs 1 Dokończyć sortowanie przez scalanie dla listy jednokierunkowej 2. Zmodyfikować to sortowanie tak aby było możliwe sortowanie listy dwukierunkowej

Pytający: 1. To nie sortowanie, to znajdowanie "środkowego" węzła w liście jednokierunkowej. 2. To nie sortowanie, to łączenie dwóch posortowanych list jednokierunkowych w jedną posortowaną listę jednokierunkową.

Mariusz: Zgadza się przedstawione przeze mnie zrzuty ekranu właśnie to przedstawiają Chodziło mi o to aby na ich podstawie napisać działające sortowanie, najpierw dla listy jednokierunkowej a później dla listy dwukierunkowej Ponieważ na pierwszym zrzucie ekranu pokazane jest wyszukiwanie głowy dla tej drugiej listy wynikowej więc musimy pamiętać także wskaźnik na poprzednika znalezionego węzła W przypadku listy jednokierunkowej dobrym pomysłem będzie wprowadzenie nowej zmiennej a w przypadku listy dwukierunkowej wskaźnik na poprzednika jest składową węzła Ten wskaźnik do poprzednika potrzebny jest do poprawnego rozdzielenia listy Teraz musimy poprawnie rozerwać listę zapamiętując przy tym głowy list wynikowych Mając funkcje rozdzielającą listy i łącząca posortowane listy można napisać funkcję sortującą Sprawdzamy czy lista zawiera więcej niż jeden element (sprawdzając głowę i jej następnika) Rozdzielamy listę uprzednio wyszukując środkowy węzeł Sortujemy rekurencyjnie obydwie połowy Łączymy dwie posortowane listy jednokierunkowe w jedną posortowaną listę jednokierunkową Dla listy dwukierunkowej rekurencyjna funkcja sortująca się nie zmienia Funkcję łączącą musimy zmienić tak aby poprawnie ustawić wskaźniki na poprzedników Funkcja rozdzielająca będzie się trochę różnić bo mamy także wskaźnik na poprzednika Jeden proponował rozdzielanie listy jednokierunkowej w ten sposób 1 zapamiętać wskaźnik na głowę listy wejściowej, 2 znaleźć węzeł, który będzie ostatnim węzłem pierwszej listy docelowej, 3 zapamiętać wskaźnik na Next węzła znalezionego w punkcie 2., 4 wpisać do Next wartość nil węzła znalezionego w punkcie 2., 5 zwrócić wskaźnik na węzeł zapamiętany w punkcie 1., jako wskaźnik na głowę pierwszej listy docelowej, 6 zwrócić wskaźnik na węzeł zapamiętany w punkcie 3., jako wskaźnik na głowę drugiej listy docelowej; a listy dwukierunkowej w ten sposób 1 zapamiętać wskaźnik na głowę listy wejściowej, 2 znaleźć węzeł, który będzie ostatnim węzłem pierwszej listy docelowej, 3 zapamiętać wskaźnik na Next węzła znalezionego w punkcie 2., 4 wpisać do Next wartość nil węzła znalezionego w punkcie 2., 5 wpisać do Prev wartość nil węzła zapamętanego w punkcie 3., 6 zwrócić wskaźnik na węzeł zapamiętany w punkcie 1., jako wskaźnik na głowę pierwszej listy docelowej, 7 zwrócić wskaźnik na węzeł zapamiętany w punkcie 3., jako wskaźnik na głowę drugiej listy docelowej; Tylko czy ten spis kroków uwzględnia też przypadki brzegowe