Given head of a singly linked list, determine whether a loop exists. A loop exists when some node can be reached again by continuously following next links.
Return true when a loop exists, otherwise return false. The linked list may be empty, contain one node, or contain many nodes.
Example 1
Input: head = [3, 2, 0, -4], pos = 1
Output: true
Explanation: Tail node connects back to node at index 1, creating a loop.
Example 2
Input: head = [1, 2, 3], pos = -1
Output: false
Explanation: Tail node points to null, so no node repeats during traversal.
Brute Force Approach
Visited node hashing uses linked list traversal and hash storage as prerequisite concepts. During traversal, every node reference is stored. Encountering an already stored reference means traversal has returned to an earlier node, so a loop exists.
Algorithm
Initialize an empty hash set to store visited node references, as the reference itself identifies whether the same node has been encountered again.
Start traversal from
headusing acurrentpointer, since every reachable node needs to be checked for repetition.Check whether the
currentnode reference already exists in the hash set, as finding the same reference again signifies that the linked list contains a cycle.Return
truewhen a repeated node reference is found, since the traversal has reached a node that was already visited.Insert the
currentnode reference into the hash set and move to the next node, as storing each visited reference allows future repetitions to be detected.Return
falsewhen traversal reachesNULL, since reaching the end means no node was revisited and therefore no cycle exists.
Dry Run
brute force cycle detect
Solution
#include <bits/stdc++.h>using namespace std;// Node structure for the singly linked list.struct ListNode { int data; ListNode* next; // Constructor to create a new node. ListNode(int value) { data = value; next = nullptr; }};class Solution {public: // Returns true if the linked list contains a cycle. bool hasCycle(ListNode* head) { // Stores addresses of all nodes visited so far. unordered_set<ListNode*> visited; // Start traversal from the head node. ListNode* current = head; // Continue until the end of the list is reached. while (current != nullptr) { // Finding the same node again means a cycle exists. if (visited.find(current) != visited.end()) { return true; } // Mark the current node as visited. visited.insert(current); // Move to the next node. current = current->next; } // Reaching nullptr means the list has no cycle. return false; }};// Creates a linked list and optionally connects the tail// back to the node at index 'pos' to form a cycle.ListNode* createList(vector<int>& arr, int pos) { // Empty array means there is no linked list. if (arr.empty()) { return nullptr; } // Create the first node and make it the head. ListNode* head = new ListNode(arr[0]); ListNode* tail = head; // Store the node where the cycle should connect. ListNode* loopNode = (pos == 0) ? head : nullptr; // Create the remaining nodes. for (int index = 1; index < (int)arr.size(); index++) { // Create and attach the next node. tail->next = new ListNode(arr[index]); tail = tail->next; // Save the node at the required cycle position. if (index == pos) { loopNode = tail; } } // Connect the tail back to the selected node if a cycle is required. if (pos != -1) { tail->next = loopNode; } return head;}// Driver code.int main() { // Linked list values. vector<int> arr = {3, 2, 0, -4}; // Cycle starts at index 1, so -4 points back to node 2. int pos = 1; // Create the linked list. ListNode* head = createList(arr, pos); Solution sol; // Check whether the linked list contains a cycle. cout << (sol.hasCycle(head) ? "true" : "false"); return 0;}Complexity Analysis
Time Complexity: O(N), where N is the total number of nodes. Each node is visited once before detecting a cycle or reaching NULL.
Space Complexity: O(N), where N is the total number of nodes. The hash set can store references to up to N nodes.
Optimal Approach
Floyd cycle detection uses two pointers moving at different speeds. Slow pointer advances by one node, while fast pointer advances by two nodes. If a loop exists, fast pointer eventually enters the same cycle and meets slow pointer.
The technique needs only pointer movement and equality comparison, so extra storage is unnecessary. If no loop exists, fast pointer reaches null or a node whose next link is null, proving that traversal can terminate normally.
Algorithm
Initialize
slowandfastpointers athead, whereslowmoves one step at a time andfastmoves twice as fast.Traverse while
fastandfast->nextexist, as these conditions ensure that the fast pointer can safely move two nodes ahead.Move
slowby one node andfastby two nodes, since a cycle will eventually cause the faster pointer to catch up with the slower pointer.Return
truewhenslowandfastmeet, as two pointers moving at different speeds can meet again only when a cycle exists.Return
falsewhenfastreaches the end of the list, since reachingNULLmeans there is no cycle connecting the nodes back to an earlier position.
Dry Run
detect loop
Solution
#include <bits/stdc++.h>using namespace std;// Node structure for the singly linked list.struct ListNode { int data; ListNode* next; // Constructor to create a new node. ListNode(int value) { data = value; next = nullptr; }};class Solution {public: // Function to detect a cycle using slow and fast pointers. bool hasCycle(ListNode* head) { // Slow moves one node at a time. ListNode* slow = head; // Fast moves two nodes at a time. ListNode* fast = head; // Continue while fast can move one more step. while (fast != nullptr && fast->next != nullptr) { // Move slow by one node. slow = slow->next; // Move fast by two nodes. fast = fast->next->next; // If both pointers meet, a cycle exists. if (slow == fast) { return true; } } // Fast reached the end, so no cycle exists. return false; }};// Function to create a linked list and optionally create a cycle.ListNode* createList(vector<int>& arr, int pos) { // Return null when the input array is empty. if (arr.empty()) { return nullptr; } // Create the first node as the head. ListNode* head = new ListNode(arr[0]); ListNode* tail = head; // Store the node where the cycle should start. ListNode* loopNode = (pos == 0) ? head : nullptr; // Create the remaining nodes. for (int index = 1; index < (int)arr.size(); index++) { // Create and attach the next node. tail->next = new ListNode(arr[index]); tail = tail->next; // Save the node at the given cycle position. if (index == pos) { loopNode = tail; } } // Connect the tail to the selected node when a cycle is required. if (pos != -1) { tail->next = loopNode; } return head;}// Driver code.int main() { // Node values of the linked list. vector<int> arr = {3, 2, 0, -4}; // Cycle starts at index 1, so -4 points back to node 2. int pos = 1; // Create the linked list. ListNode* head = createList(arr, pos); // Create the solution object. Solution sol; // Check whether the linked list contains a cycle. cout << (sol.hasCycle(head) ? "true" : "false"); return 0;}Complexity Analysis
Time Complexity: O(N), where N is the total number of nodes in the linked list; slow and fast pointers traverse at most a linear number of links.
Space Complexity: O(1), only two extra pointers are used, regardless of N.
Interview follow-up Questions
Yes. Floyd's Cycle Detection algorithm uses a slow pointer and a fast pointer to detect a loop in O(1) auxiliary space.
Be the first to add a comment.