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 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
bool hasCycle(ListNode *head) { if (head == NULL) return false; ListNode *slow = head; ListNode* *fast = head; while (slow != fast) { if (fast == Null || fast->next == NULL) { return false; } slow = slow->next; fast = fast->next->next; } return true; }
Java Code for Two Pointer Approach
public boolean hasCycle(ListNode head) { if (head == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; }
Python Code for Two Pointer Approach
def hasCycle(self, head: ListNode) -> bool: if head is None: return False slow = head fast = head.next while slow != fast: if fast is None or fast.next is None: return False slow = slow.next fast = fast.next.next 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
How do you detect a loop in a linked list?
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.
Will the fast and slow pointer always meet at some point if the list contains a cycle?
Yes, if the linked list contains a cycle, the fast and slow pointer will always meet at some point.