Zadanie rekrutacyjne #2


Zadanie rekrutacyjne – Cykl w liście jednokierunkowej

Napisz funkcje, której zadaniem jest stwierdzenie, czy lista jednokierunkowa jest poprawna, tj. czy nie zawiera cyklu. Wskaźnik do pierwszego elementu listy przekazujemy w argumencie.

Jeśli lista jest prawidłowa, ostatni wskaźnik powinien wskazywać nullptr.

Na diagramie przedstawiono przypadek negatywny

9nwXonn

Rozwiązanie naiwne

W tej implementacji trzymamy adresy wszystkich odwiedzonych węzłów listy. Jeśli do przechowywania wykorzystamy kontener o dostępie liniowym, czyli w naszym przypadku hash set, wówczas otrzymamy:

  • Liniową złożoność czasową  O(n) .
    Iterujemy raz po wszystkich elementach i za każdym razem sprawdzamy, czy podany element został już odwiedzony.
  • Niestety, otrzymamy również liniową złożoność pamięciową, co oznacza, że zapotrzebowanie na pamięć będzie zależeć od ilości elementów w liście, dodatkowo niekorzystny jest fakt, że nie znamy tej wartości na początku wywołania  M(n) .

Rozwiązanie niszczące

Chcemy pozbyć się liniowej złożoności pamięciowej. Możemy to zrobić następująco:

Ceną, jaką płacimy za jednostkową złożoność pamięciową, jest niszczenie listy.  Wskaźnik przekazany do listy nie jest typu const. Tak naprawdę powyższa funkcja sprawdza, czy lista była prawidłowa. Jeśli wyszło, że była, to możemy ponownie odwrócić wskaźniki, aby przywrócić pierwotny kształt. Konieczność modyfikowania listy jest tu największą wadą.

Rozwiązanie ostateczne

W powyższym rozwiązaniu:

  • oryginalna lista jest stała,
  • nie alokujmy dynamicznie pamięci,
  • złożoność pamięciowa jest jednostkowa,
  • złożoność czasowa jest liniowa.

Wyjaśnienie, dlaczego złożoność czasowa jest liniowa

Rozpatrzmy dwa przypadki:

  • Lista o długości n jest poprawna. Wówczas fast_ptr dojdzie w czasie (n/2) cykli do końca listy. Złożoność liniowa.
  • Lista o długości n, ma cykl o długości k. Pomiędzy początkiem cyklu a początkiem listy będzie r = n-k węzłów.
    Gdy slow_ptr dojdzie do początku cyklu, wówczas fast_ptr będzie przesunięty o pewną ilość nodów, nazwijmy to przesuniecie d.
    Możemy wyliczyć to przesuniecie z zależności  d = ( r * 2 ) DIV k .
    Oto mamy cykl i dwa wskaźniki które się “ścigają”. Jeden zawsze skacze o jedno pole, kolejny zawsze o dwa pola. Dla dowolnego przesunięcia d wskaźniki spotkają się nie później niż po dwóch okrążeniach.

2 thoughts on “Zadanie rekrutacyjne #2

  1. Jako ciekawostke mozna dodac, ze kolejnym sposobem sprawdzenia czy lista ma cykle, jest proba jej odwrocenia.

    1. odwracanie listy jest pokazane w “Rozwiązanie niszczące”

Dodaj komentarz

Twój adres email nie zostanie opublikowany.