ronith
7/7/2018 - 4:31 AM

Find length of loop in linked list

We know that Floyd’s Cycle detection algorithm terminates when fast and slow pointers meet at a common point. We also know that this common point is one of the loop nodes. We store the address of this in a pointer variable say ptr2. Then we start from the head of the Linked List and check for nodes one by one if they are reachable from ptr2. When we find a node that is reachable, we know that this node is the starting node of the loop in Linked List and we can get pointer to the previous of this node.

Find length of loop in linked list.cpp
content_copyfile_download
//https://www.geeksforgeeks.org/find-length-of-loop-in-linked-list/
#include<iostream>
#include<list>
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;
}

int CountLoop (node* n) {
    int len = 1;
    node* temp = n;
    while (temp->next != n){
        len++;
        temp = temp->next;
    }
    return len;
}

int DetectLoop (node* head) {
    node *slow=head, *fast=head,*ptr;
    while (slow && fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast)
            return CountLoop (slow);
    }
}

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);
    }
    head->next->next->next->next->next = head->next;
    cout<< "Length of Loop is " << DetectLoop(head);
}