Notatnik techniczny

Zadanie rekrutacyjne #2

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 Odwracanie listy

using namespace std;
 
struct List_node
{
    List_node* next_node;
    void* data;
};
 
bool Sprawdz_liste( const List_node* node )
{
    ...................
}

Rozwiązanie naiwne

#include <unordered_set>

bool Sprawdz_liste( const List_node* node )
{
    unordered_set<const List_node*> db;
    while ( node != nullptr ) {
        if ( db.find( node ) != db.end())
            return false;
        db.insert ( node );
        node = node->next_node;
    }
    return true;
}

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:

bool Sprawdz_liste_2( List_node* node )
{
    if ( !node )
        return true;
    const List_node* start_node = node;
 
    List_node* prev_node = node;
    node = node->next_node;
    while ( node != start_node ) {
        if ( node == nullptr )
            return true;
 
        List_node* temp = node->next_node;
        node->next_node = prev_node;
        prev_node = node;
        node = temp;
    }
    return false;
}

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

bool Sprawdz_liste_3( const List_node* node )
{
    if ( !node )
        return true;
    const List_node* fast_ptr = node;
    const List_node* slow_ptr = node;
 
    do {
        fast_ptr = fast_ptr->next_node;
        if ( fast_ptr == nullptr )
            return true;
        fast_ptr = fast_ptr->next_node;
        if ( fast_ptr == nullptr )
            return true;
        slow_ptr = slow_ptr->next_node;
    } while ( fast_ptr != slow_ptr );
    return false;
}

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.