Remove Loop From Linked List using Floyd's Algorithm

C++ Code:

void remove_loop(Node *head){

    Node *slow = head;

    Node *fast = head;

    if (!head || !(head->next))

        return;

    while(slow && fast && fast->next){

        slow = slow->next;

        fast = fast->next->next;

        if(slow == fast)

            break;

    }

    

    // No Loop exixts

    if (slow != fast){

        std::cout << "No Loop" << std::endl;

        return;

    }

    

    // When Loop exists

    slow = head;

    while(slow->next != fast->next){

        slow = slow->next;

        fast = fast->next;

    }

    fast->next = nullptr;

}

Detailed explanation is available on Youtube:

Subscribe to KnowledgeCenter

Why Floyd's Loop Detection Algorithm works ?

For detailed Explanation watch the youtube video:

Subscribe to KnowledgeCenter

Find the middle element of a Linked List

void print_middle(Node *head){

    Node *fast = head;

    Node *slow = head;

    while(fast && fast->next){

        fast = fast->next->next;

        slow = slow->next;

    }

    std::cout << slow->data << std::endl;

}

Watch the detailed explanation of the concepts on Youtube:

Subscribe to KnowledgeCenter

Find the Length of Loop in Linked List

We modify the Floyd's Loop/Cycle Detection Algorithm that we saw in the previous Post to find the count of Nodes which are part of the Linked List.

int count_loop_lenth(Node *node){

    int count = 1;

    Node *curr = node;

    while(curr->next != node){

        curr = curr->next;

        ++count;

    }

    return count;

}

int detect_loop_floyd(Node *head){

    Node *slow = head;

    Node *fast = head;

    while(slow && fast && fast->next){

        slow = slow->next;

        fast = fast->next->next;

        if(slow == fast){

            return count_loop_lenth(slow);

        }

    }

    return 0;

}

Watch detailed Explanation on Youtube.

Subscribe to KnowledgeCenter