Zadanie rekrutacyjne #2

Cykl w liście jednokierunkowej

Napisz funkcję, 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.

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;
}

Trzymamy adresy wszystkich odwiedzonych węzłów. Jeśli do przechowywania wykorzystamy kontener o dostępie liniowym, czyli w naszym przypadku hash set (opens new window), wówczas otrzymamy:

• Liniową złożoność czasową O(n).
• Niestety, również liniową złożoność pamięciową, 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ą ponosimy 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.
• Dwa wskaźniki, ścigają się. Jeden skacze o jedno pole, kolejny zawsze o dwa pola.

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

Rozpatrujemy 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.