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 core challenge of this problem is to detect if a linked list contains a cycle. A cycle occurs when a node's next pointer points back to a previous node, creating a loop. This problem is significant in various applications, such as detecting infinite loops in programs or ensuring data structures are correctly formed.
Potential pitfalls include misunderstanding the problem constraints or not handling edge cases like an empty list or a single node without a cycle.
To solve this problem, we can use Floyd's Tortoise and Hare algorithm, which is an efficient way to detect cycles in a linked list using two pointers.
A naive solution would involve using a hash set to keep track of visited nodes. While this works, it requires O(n) extra space, which is not optimal.
Floyd's Tortoise and Hare algorithm uses two pointers, one moving twice as fast as the other. If there is a cycle, the fast pointer will eventually meet the slow pointer. This approach only requires O(1) extra space.
1. Initialize two pointers, slow and fast, both pointing to the head of the list.
2. Move the slow pointer one step at a time and the fast pointer two steps at a time.
3. If the fast pointer reaches the end (null), there is no cycle.
4. If the slow pointer and fast pointer meet, a cycle exists.
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool hasCycle(ListNode *head) {
if (head == nullptr) return false;
ListNode *slow = head;
ListNode *fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next; // Move slow pointer by 1 step
fast = fast->next->next; // Move fast pointer by 2 steps
if (slow == fast) {
return true; // Cycle detected
}
}
return false; // No cycle
}
};
The time complexity of Floyd's Tortoise and Hare algorithm is O(n) because, in the worst case, we might need to traverse the entire list. The space complexity is O(1) since we only use two pointers.
1. An empty list (head is null) should return false.
2. A single node without a cycle should return false.
3. A single node with a cycle (node points to itself) should return true.
To test the solution comprehensively, consider the following cases:
When approaching such problems, it's essential to understand the data structure and the problem constraints. Visualizing the problem with diagrams can help. Practice solving similar problems and study different algorithms to improve problem-solving skills.
Detecting a cycle in a linked list is a common problem with practical applications. Understanding and implementing Floyd's Tortoise and Hare algorithm provides an efficient solution with O(n) time complexity and O(1) space complexity.