Detect Loop in Linked List

Problem Statement

Given a linked list, check whether the linked list is having a loop or not(detect loop in linked list). A cycle exists in a linked list if it contains a node that may be accessed again by following the next pointer.

Example

Input:

Output: True

Explanation: linked list is having 6 nodes and the next pointer of the last node is pointing to the 3rd node which indicates the loop in the linked list.

Input:

Output: True

Constraints

1<=length of linked list<=10000 1<=Data of Node<=1000

Approach 1: HashSet Approach

We can detect loop in linked list using the HashSet Approach. Traverse the linked list one by one, adding node addresses to a HashMap as you go. If NULL is reached at any point, return False as the end of linked list is reached and it doesn't have any loop. If any previously node address is pointed by the current node, just return True.

Complexity Analysis

Time Complexity: O(N) => Only one traversal of loop is needed. Space Complexity: O(N) => N space for storing N nodes in HashMap.

C++ Implementation

Java Implementation

Python Implementation

Approach 2: Modifying the Linked List Data Structure

We can detect loop in linked list by modifying the Linked List Data Structure. This approach removes the space required for storing values in hashmap, By modifying the linked list data structure. The linked list definition will contain a flag variable that marks the visited node:

• Traverse the Linked list.
• For every node make the flag variable one.
• If the already existing node is accessed return true.
• if null or the end of the linked list is reached return false

Complexity Analysis

Time Complexity: O(N) => Only one traversal of loop is needed. Space Complexity: O(1)

C++ Implementation

Java Implementation

Python Implementation

Approach 3: Floyd’s Cycle

We can detect loop in linked list using the Floyd's Cycle. This is the fastest method for detecting a loop in a linked list:

• Traverse the linked list using two pointers, a fast pointer, and a slow pointer starting from the first node.
• Now in a loop move the fast pointer by 2 nodes and the slow pointer by 1 node.
• If both the pointers point to a same node then loop is detected and return true, else if fast pointer details the end of the linked list return false

Complexity Analysis

Time Complexity: O(N) => Only one traversal of loop is needed. Space Complexity: O(1)

C++ Implementation

Java Implementation

Python Implementation

Approach 4: Marking visited nodes without modifying the linked list data

We can detect loop in linked list by marking visited nodes without modifying the linked list data. A temporary node is created in this method. Each node that is traversed has its next pointer set to this temporary node:

• The next pointer of a node is used as a visited flag to indicate whether or not the node has been visited.
• Every node is examined to see if the next node is pointing to a temporary node.
• In the case of the loop's first node, this condition will be true the second time we traverse it, indicating that the loop exists.

Complexity Analysis

Time Complexity: O(N) => Only one traversal of loop is needed. Space Complexity: O(1)

C++ Implementation

Java Implementation

Python Implementation

Approach 5: Store length

we can detect loop in linked list by storing length. Two pointers are formed in this method: the first (which always points to the head) and the last. When the last pointer moves, we calculate the number of nodes between the first and last nodes and check whether the current number of nodes is greater than the previous number of nodes; if it is, we move the last pointer; otherwise, we've reached the end of the loop, and we return output accordingly.

Complexity Analysis

Time Complexity: O(N^2) => traversal of pointers * traversal for distance at every iteration. Space Complexity: O(1)

C++ Implementation

Java Implementation

Python Implementation