# Detect Loop in Linked List

## Problem Statement

Given a linked list. Determine if the linked list has a cycle in it.

A linked list contains a cycle if it consists of a node that can be reached again by continuously following the next pointer.

Examples:

Input:

Output: True
Explanation:

The linked list consists of a loop, where the last node connects to the second node.

Input:

Output: True

## HashSet Approach

The simplest approach to solve this problem is to check whether a node in the linked list has been visited before. To perform this operation, a hashmap can be used.

Algorithm

• Initialise a hashmap.
• If the current node is already present in the hashset, it ensures that the linked list contains a loop. Hence, terminate and return True.
• Else, continue traversing and continue inserting the node into the hashset.
• Return False if it doesn’t satisfy the above conditions.

### C++ Implementation

```bool hasCycle(Node* head) {
set<Node*> mp;
return true;
}
}
return false;
}```

### Java Implementation

``` public boolean hasCycle(ListNode head) {
Set<ListNode> mp = new HashSet<>();
return true;
}
}
return false;
}```

### Python Implementation

```def hasCycle(head):
mp = set()
return True
return False```

Time Complexity: O(N) where N is the number of nodes of the linked list.
Space Complexity: O(N), as HashSet is used

## Floyd’s Cycle Detection Algorithm

This approach uses a two-pointer – a fast pointer and a slow pointer to determine if there exists a cycle in the loop. The slow pointer moves one node ahead at a time, while the fast pointer moves two nodes ahead at a time.

If a loop exists in the linked list, the fast and slow pointers are bound to meet at some point.

Algorithm:

• Initialise two pointers, fast and slow to the head of the linked list.
• Traverse through the linked list until the fast pointer doesn’t reach the end of the linked list.
• If the fast pointer reaches the end, it means that the linked list doesn’t contain any cycle. Hence, return False.
• Else, move the slow pointer by one node i.e. slow = slow -> next and fast pointer by two nodes i.e. fast = fast -> next -> next.
• At any point, if the fast and the slow pointers point to the same node, return True as a loop has been detected.

### C++ Code for Two Pointer Approach

```// C++ Code
return false;
do {
if (fast == Null || fast->next == NULL) {
return false;
}
slow = slow->next;
fast = fast->next->next;
} while (slow != fast);
return true;
}```

### Java Code for Two Pointer Approach

```// JAVA Code
return false;
}
do {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
} while (slow != fast);
return true;
}```

### Python Code for Two Pointer Approach

```// PYTHON Code
def hasCycle(self, head: ListNode) -> bool:
return False
while True:
if fast is None or fast.next is None:
return False
slow = slow.next
fast = fast.next.next
if(slow == fast)
return True
return True```
• Time Complexity: O(N), where N is the number of nodes of the linked list.
• Space Complexity: O(1), as a map is used.

## Practice Question

### Q.1: How do you detect a loop in a linked list?

Ans: A loop can be detected efficiently using the fast and slow pointer algorithm, where the fast pointer moves by two nodes and the slow pointer move by one node at a time.

### Q.2: Will the fast and slow pointer always meet at some point if the list contains a cycle?

Ans: Yes, if the linked list contains a cycle, the fast and slow pointer will always meet at some point.  