Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.
Constraints:
[0, 104].-105 <= Node.val <= 105pos is -1 or a valid index in the linked-list.Follow up: Can you solve it using O(1) (i.e. constant) memory?
The Linked List Cycle problem asks whether a linked list contains a loop where a node eventually points back to a previously visited node. Detecting such cycles is important for avoiding infinite traversals and ensuring correct list processing.
One intuitive strategy is using a Hash Table. As you traverse the list, store each visited node in a set. If you encounter a node that already exists in the set, a cycle is present. This approach is easy to implement and clearly tracks visited nodes.
A more optimized method uses the Two Pointers technique, commonly known as Floyd’s Cycle Detection (Tortoise and Hare). In this approach, one pointer moves one step at a time while another moves two steps. If a cycle exists, the fast pointer will eventually meet the slow pointer inside the loop.
The two-pointer technique is typically preferred because it achieves O(1) space complexity while maintaining linear time traversal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Table (Visited Nodes) | O(n) | O(n) |
| Two Pointers (Floyd’s Cycle Detection) | O(n) | O(1) |
NeetCode
The Floyd's Tortoise and Hare algorithm is a two-pointer technique that is used to detect cycles in a linked list. The approach involves using two pointers, one moving twice as fast as the other. If there's a cycle, the fast pointer will eventually meet the slow pointer. This method works in O(n) time with O(1) space.
Time Complexity: O(n), where n is the number of nodes in the list.
Space Complexity: O(1), constant space usage.
1#include <stdbool.h>
2
3struct ListNode {
4 int val;
5 struct ListNode *next;
6};
In this solution, we create two pointers, slow and fast. The slow pointer moves one step at a time while the fast moves two steps. If the list contains a cycle, these pointers will eventually meet inside the cycle. If there's no cycle, fast or fast->next will become null.
This approach uses a HashSet to track the nodes visited during the traversal. If a node is encountered twice, there is a cycle. This method requires O(n) space but is simpler to understand.
Time Complexity: O(n^2) because of nested loops (non-optimal use of memory).
Space Complexity: O(n), where n is the number of nodes (uses additional storage).
1using System.Collections.Generic;
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public bool HasCycle(ListNode head) {
HashSet<ListNode> visited = new HashSet<ListNode>();
while (head != null) {
if (visited.Contains(head)) return true;
visited.Add(head);
head = head.next;
}
return false;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Linked List Cycle is a common interview question at companies like Google, Amazon, and Meta. It tests understanding of linked lists, pointer manipulation, and the efficient use of the two-pointer technique.
The optimal approach uses Floyd’s Cycle Detection algorithm with two pointers. One pointer moves one step while the other moves two steps. If the list has a cycle, the two pointers will eventually meet, confirming the presence of a loop with O(1) space.
In a cyclic list, the faster pointer moves through the loop more quickly than the slow pointer. Eventually, their paths intersect within the cycle, guaranteeing a meeting point that confirms the presence of a loop.
A hash set is a simple data structure for detecting cycles because it stores visited nodes during traversal. If a node appears again in the set, a cycle exists. However, the two-pointer technique is more space-efficient.
The C# solution follows a logical pattern applying HashSet to track all encountered nodes. Cycle detection occurs when a node reappears in the set.