CareerCup

Have two pointers pointing to the linked list incrementing at different pace. Ptr1 increments each node and ptr2 increments every two nodes. If there is a cycle, eventually ptr1 == ptr2.

#include <iostream>
#include <list>

using namespace std; 

#define MAX 5

template<class T>
class Node {
public: 

    Node(): next(NULL) {};
    Node(T d): data(d), next(NULL) {};
    T data; 
    Node *next; 
};

template <class T>
bool hasCycle(Node<T> *n, Node<T> **me = 0) {

    if (n == NULL) return false; 
    Node<T> *ptr1 = n; 
    Node<T> *ptr2 = n->next; 
    
    while (ptr2 && (ptr2->next)) {
        if (ptr1 == ptr2) { 
            *me = ptr1; 
            return true; 
        } 
        ptr1 = ptr1->next; 
        ptr2 = ptr2->next->next; 
    }
    return false; 
}

int main() {
    
    Node<int> *head = new Node<int>(0); 
    Node<int> *tmp = head, *tmp1 = NULL; 
    Node <int> **me = NULL; 
    
    // Case 1: NULL
    cout << "Case 1 cycle: " << hasCycle<int>(tmp1) << "\n"; 
    
    // Case 2: 0 -> NULL
    cout << "Case 2 cycle: " << hasCycle<int>(tmp) << "\n"; 

    // Case 3: 0 -> 1 -> NULL
    tmp = head; 
    for (int i=1; i<2; i++) {
        tmp1 = new Node<int>(i);
        tmp->next = tmp1; 
    }
    cout << "Case 3 cycle: " << hasCycle<int>(tmp) << "\n"; 

    // Case 4: 0 loops
    tmp = head; 
    tmp->next = tmp; 
    cout << "Case 4 cycle: " << hasCycle<int>(tmp, &tmp1) << " at: " << tmp1->data << "\n"; 
    
    // Case 5: 0 -> 1 -> loops to 0
    tmp = head; 
    for (int i=1; i<2; i++) {
        tmp1 = new Node<int>(i);
        tmp->next = tmp1; 
        tmp = tmp->next; 
    }
    tmp->next = head; 
    
    cout << "Case 5 cycle: " << hasCycle<int>(head, &tmp1) << " at: " << tmp1->data << "\n"; 

    // Case 6: 0 -> 1 -> 2 -> loops to 1
    tmp = head; 
    for (int i=1; i<3; i++) {
        tmp1 = new Node<int>(i);
        tmp->next = tmp1; 
        tmp = tmp->next; 
    }
    tmp->next = head->next; 
    
    cout << "Case 6 cycle: " << hasCycle<int>(head, &tmp1) << " at: " << tmp1->data << "\n"; 
    
    // Case 7: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> loops to 5
    tmp = head; 
    for (int i=1; i<11; i++) {
        tmp1 = new Node<int>(i);
        tmp->next = tmp1;
        tmp = tmp->next;  
    }
    tmp->next = head->next->next->next->next->next; 
    
    cout << "Case 7 cycle: " << hasCycle<int>(head, &tmp1) << " at: " << tmp1->data << "\n"; 
    
        
    return 0;

}