Detect Loop in linked list

Given a linked list of N nodes. The task is to check if the the linked list has a loop. Linked list can contain self loop.

Example 1:

Input:

N = 3

value[] = {1,3,4}

x = 2

Output: True

Explanation: In above test case N = 3.

The linked list with nodes N = 3 is

given. Then value of x=2 is given which

means last node is connected with xth

node of linked list. Therefore, there

exists a loop.

Example 2:

Input:

N = 4

value[] = {1,8,3,4}

x = 0

Output: False

Explanation: For N = 4 ,x = 0 means

then lastNode->next = NULL, then

the Linked list does not contains

any loop.

method 1:

traverse through whole linked list 

and mark the node data with -1

now check everytime if the node data is -1 

if it is -1 than loop exits

c++ implementation:

bool detectLoop(Node* head)
{
   Node *temp=head;
   
   while(temp->data!= -1  && temp->next!=NULL)
   {
       temp->data=-1;
       temp=temp->next; 
    }
    
    if(temp->data==-1) 
    return 1;
    else
    return 0;
}

Time Complexity: O(n)  

method 2:

create two pointers: fast and slow.

point both of them to head at first.

Now, slow moves by one position and fast moves by two position. If these two pointers meet at some time then loop exists. If we reach null without any meeting then no loop exists.

c++ implementation:

bool detectLoop(Node* head)
{
   Node *slow_p = head, *fast_p = head;
 
    while (fast_p && fast_p->next) 
    {
        slow_p = slow_p->next;
        fast_p = fast_p->next->next;
        if (slow_p == fast_p) 
            return 1;
    }
    return 0;
}

Time Complexity: O(n)