Odwracanie pojedynczo połączonej listy [Java] - java, pojedynczo-połączona lista

Zastanawiałem się, czy ktoś mógłby pomóc wyjaśnić, w jaki sposóbodwrócić listę pojedynczo połączoną bez tworzenia nowych węzłów lub zmieniania danych w istniejących węzłach. Próbuję uczyć się o finały i mieliśmy to pytanie na poprzednim teście. Nie wydają odpowiedzi na części kodujące testu i nie udało mi się tego rozgryźć.

Powiedzieli nam, że najlepszym sposobem na odwrócenie tego byłoużywając "techniki biegacza", która, jak sądzę, rozumiem, co to jest. Opisali to jako użycie dwóch wskaźników lub liczników, aby przejrzeć listę i zebrać informacje, ale nie jestem pewien jak tego użyć, aby odwrócić listę, która jest mi jak najbardziej podobna, Udało mi się zastosować brutalny kod, aby odwrócić listę o długości 2, 3 i 4, ale nie byłem w stanie wykonać pętli lub wykonać rekursywnie, ponieważ każdy kod lub wyjaśnienie, jak to zrobić, byłby mile widziany, dziękuję.

Odpowiedzi:

Możesz wyprowadzić kod, zaczynając od idei po prostu - jeden po drugim - wyskakując elementy z listy wejściowej i wciskając je na początkowo pustą listę wyników:

NODE reverse(NODE list) {
NODE result = null;
while (list != null) {
NODE head = <pop the first node off list>
<push head onto result>
}
return result;
}

Wynik będzie odwrotnością wejścia. Teraz zastąp Javę brakującymi elementami

NODE reverse(NODE list) {
NODE result = null;
while (list != null) {
// pop
NODE head = list;
list = list.next;
// push
head.next = result;
result = head;
}
return result;
}

I jesteś skończony...

To zależy od twojej implementacji listy, ale powracałbym do końca, a następnie odwracałam referencje.

void Reverse(List pList) {
Reverse(pList, null, pList.First); // initial call
}

void Reverse(List pList, Node pPrevious, Node pCurrent) {
if (pCurrent != null)
Reverse(pList, pCurrent, pCurrent.Next);   // advance to the end

else { // once we get to the end, make the last element the first element
pList.First = pPrevious;
return;
}

pCurrent.Next = pPrevious; // reverse the references on all nodes
}