Given the reference (pointer) to the head node of a linked list, the task is to check if the linked list has a loop.
A linked list can contain a self-loop as well.
Input: 1->2->3->4->5->2
Output: true
Input: 1->2->3->4->5->NULL
Output: false
Solutions
Method 1: Floyd's Cycle-Finding Algorithm - O(n) time and O(1) space
In Floyd's Cycle-Finding Algorithm, we traverse a linked list using two pointers.
Move one pointer(slow) by one and another pointer(fast) by two nodes.
If these pointers meet at the same node, then there is a loop.
If pointers do not meet, then the linked list doesn't have a loop.
Complexity
This solution has a time complexity of O(n) and a space complexity of O(1).
Method 2: Without Modifying Nodes - O(n) time and O(1) space
In this method, a temporary node is created.
While traversing the list, each node's next, points to this temporary node.
If we come across a node that points to the temporary node, that means the has a cycle and if any node points to null, then the loop doesn't exist.
Complexity
This solution has a time complexity of O(n) and a space complexity of O(1).
Method 3: Using Map - O(n) time and O(1) space
In this solution, we need to traverse the list while storing the addresses of visited nodes in a hash.
For any node, if the reference is already present in the hash, then there is a loop.
Complexity
This solution has a time complexity of O(n) and a space complexity of O(n).
Method 4: By Modifying Nodes - O (n) time and O(1) space
The idea is to modify the nodes of the linked list by having a visited flag (boolean visited) with each node.
Traverse through the linked list from the head node and mark "visited=true".
If any node already has "visited=true", that means the node is already visited and the list has a loop.
If the list is exhausted without detecting "visited=true", that means the list does not have any loop.
This solution works in O(n) time but requires additional information with each node.
Complexity
This solution has a time complexity of O(n) and a space complexity of O(1).