ronith
7/6/2018 - 7:07 PM

Detect loop in a linked list

Given a linked list, check if the the linked list has loop or not. Use Hashing: Traverse the list one by one and keep putting the node addresses in a Hash Table. At any point, if NULL is reached then return false and if next of current node points to any of the previously stored nodes in Hash then return true.


Floyd’s Cycle-Finding Algorithm: This is the fastest method. Traverse linked list using two pointers. Move one pointer by one and other pointer by two. If these pointers meet at some node then there is a loop. If pointers do not meet then linked list doesn’t have loop.

// https://www.geeksforgeeks.org/detect-loop-in-a-linked-list/
#include <bits/stdc++.h>
using namespace std;

struct linked_list {
    int data;
    struct linked_list* next;
};
typedef struct linked_list node;

node* insert (node* head, int n) {
    node* list = (node*)malloc(sizeof(node*));
    list->data=n;
    list->next=head;
    head=list;
    return head;
}

bool DetectLoop (node* head) {
    node *slow = head, *fast = head;
    while (slow && fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
     if (slow == fast)
        return 1;
    }
    return 0;
}

int main () {
    int n;
    node* head=NULL;
    while (true) {
        cout<< "Enter the element, enter -9 to stop: ";
        cin>>n;
        if (n==-9)
            break;
        else
            head = insert(head,n);
    }
    if (DetectLoop(head) == 0)
        cout<< "Loop not detected";
    else
        cout<< "Loop detected!";
}
// https://www.geeksforgeeks.org/detect-loop-in-a-linked-list/
#include <bits/stdc++.h>
using namespace std;

struct linked_list {
    int data;
    struct linked_list* next;
};
typedef struct linked_list node;

node* insert (node* head, int n) {
    node* list = (node*)malloc(sizeof(node*));
    list->data=n;
    list->next=head;
    head=list;
    return head;
}

bool DetectLoop (node* head) {
    unordered_set <node*> s;
    while (head!=NULL) {
        if (s.find(head) != s.end())
            return 1;
        s.insert(head);
        head = head->next;
    }
    return 0;
}

int main () {
    int n;
    node* head=NULL;
    while (true) {
        cout<< "Enter the element, enter -9 to stop: ";
        cin>>n;
        if (n==-9)
            break;
        else
            head = insert(head,n);
    }
    if (DetectLoop(head) == 0)
        cout<< "Loop not detected";
    else
        cout<< "Loop detected!";
}