usłyszałem pytanie Wywiad: „Broszura do pojedynczo-połączonej listy do tyłu, w stałym czasie i przestrzeni liniowej”Drukuj pojedynczo-połączonej listy do tyłu, w stałym czasie i przestrzeni liniowej
Moje rozwiązanie polegało na odwróceniu listy odsyłaczy i wydrukowaniu jej w ten sposób. Czy istnieje inne rozwiązanie, które nie jest destrukcyjne?
Jeśli odwrócić go ponownie po wydrukowaniu nie będzie już być destrukcyjne, ponieważ oryginalny porządek zostanie przywrócony.
Można użyć wywołania rekursywnego w łańcuchu połączonych list z odniesieniem do tego, co chcesz napisać. Każdy węzeł używałby funkcji drukowania węzła podrzędnego podczas przekazywania referencji przed samym drukowaniem.
W ten sposób każdy węzeł na liście przejdzie w dół, dopóki ostatni nie będzie mógł i przejdzie od razu do zapisu, a następnie każdy z powrotem do łańcucha będzie pisać po ostatnim z powrotem do przodu .
Edit
To faktycznie nie pasuje widowisko ze względu na przestrzeni liniowej na stosie. Jeśli masz coś na zewnątrz, aby przejść funkcje i metodę pisania na przód łańcucha, logika podstawowa może nadal działać.
Ale byłoby to miejsce O (n) stosu =/ –
To jest przestrzeń liniowa - stos liczy się jako spacja. –
@Razor - lol, jesteś tylko trochę szybszy na klawiaturze. –
Po prostu wykonaj iterację i wydrukuj ją po drodze, ale odwróć monitor do góry nogami.
˙uoıʇɐɯɹoɟsuɐɹʇ ʇxǝʇ ǝlʇʇıl ɐ ɥʇıʍ ʇɥƃıɹ ʇsoɯlɐ ʞool uɐɔ ʇI
LOL najlepsze rozwiązanie jak na razie –
Aw człowieku, pobił mnie do tego. –
Oto niekonwencjonalne podejście: Zmień konsolę na kolejność czytania od prawej do lewej, a następnie wydrukuj listę w normalnej kolejności. Pojawią się w kolejności wstecznej. Konieczność wizyty w rzeczywistych danych w odwrotnej kolejności nie brzmi jak ograniczenie tego problemu.
Już zrozumiałeś większość odpowiedzi: cofnij połączoną listę w miejscu i przejdź z powrotem na początek listy, aby ją wydrukować. Aby nie być (trwale) niszczycielem, ponownie odwróć listę połączoną w miejscu , gdy przechodzisz ją z powrotem na początek i drukujesz.
Zauważ jednak, że działa to tylko wtedy, gdy masz tylko jeden wątek wykonania lub całe przejście jest sekcją krytyczną, tak że działa tylko jeden wątek (tzn. Drugi wątek nie może nigdy zagrać lista w środku przejścia).
Obie pierwsze dwie odpowiedzi dokładnie odpowiadają na to pytanie. Wybrałem ten drugi, ponieważ został opublikowany wcześniej. Ale głosowałem za tym, ponieważ ma więcej szczegółów. Szkoda, SO nie pozwól mi zaakceptować więcej niż jednej odpowiedzi, jeśli są bardzo podobne: [ –
OK, może to być pytanie do wywiadu, ale w rzeczywistości jest to kwestia związana z algorytmem Weis. Pytanie jasno stwierdza, że nie możemy używać rekurencji (coś, co przesłuchujący ukryje i ujawni później), ponieważ rekurencja nie będzie wykorzystywała stałej przestrzeni, a rekursja moslty stanie się głównym punktem dyskusji w przyszłości. Rozwiązaniem jest drukowanie wsteczne i cofanie.
Tak właśnie myślałem. Czy jest to dobra praktyka w realnej sytuacji?(Zakładając przejście przez odniesienie) –
Właściwie można by go najpierw odwrócić bez drukowania, a następnie wydrukować, a następnie ponownie go odwrócić. – x4u
@Razor: ish. Zwykle, jeśli przekażesz coś do druku, możesz oczekiwać, że odwiedzający potraktuje to jako niemodyfikowalne. Tak więc w językach, które dbają o takie rzeczy, albo funkcja musi (niespodziewanie) wziąć parametr inny niż const, albo sama funkcja musi zawierać const-unsafe code. Musiałbyś zdecydować, czy korzyści są warte dodatkowego ryzyka napisania niepoprawnego kodu, czy lepiej byłoby zrobić odwróconą kopię listy lub użyć zamiast tego struktury dwukierunkowej (np. Lista podwójnie związana). Jeśli jest to wystarczająco poważna korzyść, wszystko jest dobrą praktyką ;-) –