Jak określić, czy lista połączona ma cykl, używając tylko dwóch miejsc pamięci

Możesz użyć algorytmu żółwia i królika.

Wikipedia też ma wyjaśnienie i nazywają to "algorytmem znajdowania cyklu Floyda " lub "żółw i zając"

Absolutnie. Jednym z rozwiązań rzeczywiście może być przemierzanie listy z obu wskaźników, jeden podróżuje z dwukrotnym tempem drugiego.

Zacznij od "powolnego" i "szybkiego" wskaźnika wskazującego dowolne miejsce na liście. Uruchom pętlę trawersową. Jeśli wskaźnik "szybki" w dowolnym momencie pokrywa się ze wskaźnikiem wolnym, masz okrągłą listę połączoną.

int *head = list.GetHead();
if (head != null) {
    int *fastPtr = head;
    int *slowPtr = head;

    bool isCircular = true;

    do 
    {
        if (fastPtr->Next == null || fastPtr->Next->Next == null) //List end found
        {
            isCircular = false;
            break;
        }

        fastPtr = fastPtr->Next->Next;
        slowPtr = slowPtr->Next;
    } while (fastPtr != slowPtr);

    //Do whatever you want with the 'isCircular' flag here
}

Próbowałem rozwiązać ten sam i znalazłem inne (mniej efektywne, ale nadal optymalne) rozwiązanie.

Idea opiera się na odwróceniu listy pojedynczo połączonej w czasie liniowym. Można to zrobić, wykonując dwa swapy na każdym kroku iteracji listy. Jeśli q jest poprzednim elementem (początkowo null), A P jest bieżącym, swap(q,p->next) swap(P,q) odwróci łącze i przesunie Dwa wskaźniki w tym samym czasie. Swapy można wykonać za pomocą XOR, aby zapobiec konieczności korzystania z trzeciej pamięci miejsce.

Jeśli lista ma cykl, to w pewnym momencie podczas iteracji dotrzesz do węzła, którego wskaźnik został już zmieniony. Nie możesz wiedzieć, który to węzeł, ale kontynuując iterację, zamieniając kilka elementów dwukrotnie, ponownie trafiasz na początek listy.

Odwracając listę dwukrotnie, lista pozostaje niezmieniona w wyniku i możesz stwierdzić, czy miała cykl na podstawie tego, czy dotarłeś do pierwotnego początku listy, czy nie.

int isListCircular(ListNode* head){
    if(head==NULL)
        return 0;
    ListNode *fast=head, *slow=head;
    while(fast && fast->next){
        if(fast->next->next==slow)
            return 1;
        fast=fast->next->next;
        slow=slow->next;
    }
    return 0;
}

Przejście tego problemu do następnego kroku będzie oznaczeniem cyklu (czyli nie tylko tego, że cykl istnieje, ale gdzie dokładnie znajduje się na liście). Algorytm żółwia i zająca może być używany do tego samego, jednak będziemy wymagać śledzenia głowy listy przez cały czas. Ilustrację tego algorytmu można znaleźć tutaj .

boolean findCircular(Node *head)
{
Node *slower, * faster;
slower = head;
faster = head->next;
while(true) {


 if( !faster || !faster->next)
   return false;

 else if (faster == slower || faster->next == slower)
    return true;
 else{

    faster = faster->next->next;
   }
}
}