Saturday, April 13, 2019

Detect Loop in a Linked List



Method 1: (Hashing)


bool detect_loop_map(Node *head){

    std::unordered_map<Node*, bool> visited;
    Node *curr = head;
    while(curr){
        if (visited[curr] == true)
            return true;
        visited[curr] = true;
        curr = curr->next;
    }
    return false;

}

Method 2:(Floyd's Cycle Detection)


bool 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 true;
        }
    }
    return false;

}

Watch detailed explanation on Youtube:



Visit our Youtube playlist for Linked List: https://www.youtube.com/playlist?list=PL1w8k37X_6L-bwZCPpELH6Cwo3WzUxDp7

Subscribe to KnowledgeCenter

2 comments:

LeetCode 30 Day Challenge | Day 7 | Counting Elements

Given an integer array  arr , count element  x  such that  x + 1  is also in  arr . If there're duplicates in  arr , count them sepe...