- Problem Statement
- HashSet Approach
- Floyd’s Cycle Detection Algorithm
- C++ Code for Two Pointer Approach
- Java Code for Two Pointer Approach
- Python Code for Two Pointer Approach
- Practice Question
- Frequently Asked Questions
- Q.1: How do you detect a loop in a linked list?
- Q.2: Will the fast and slow pointer always meet at some point if the list contains a cycle?
- Additional Resources
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:
Confused about your next job?
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.
- Traverse the linked list till the head pointer isn’t NULL:
- 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;
while (head != null) {
if (mp.find(head) != mp.end()) {
return true;
}
mp[head]++;
head = head->next;
}
return false;
}Java Implementation
public boolean hasCycle(ListNode head) {
Set<ListNode> mp = new HashSet<>();
while (head != null) {
if (mp.contains(head)) {
return true;
}
mp.add(head);
head = head.next;
}
return false;
}Python Implementation
def hasCycle(head):
mp = set()
while head is not None:
if head in mp:
return True
mp.add(head)
head = head.next
return FalseTime 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
bool hasCycle(ListNode *head) {
if (head == NULL)
return false;
ListNode *slow = head;
ListNode* *fast = head;
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
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
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:
if head is None:
return False
slow = head
fast = head.next
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
Frequently Asked Questions
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.
