Problem Statement:
Given head, the head of a linked list, determine if the linked list has a cycle in it.
Return true if there is a cycle; otherwise, return false.
Examples:
- Input: head = [3,2,0,-4], pos = 1
Output: true - Input: head = [1,2], pos = 0
Output: true - Input: head = [1], pos = -1
Output: false
Constraints:
- The number of nodes is in the range [0, 10⁴].
- -10⁵ ≤ Node.val ≤ 10⁵
posis -1 or a valid index in the linked list.
Approach:
- Use a
Setto track visited nodes. - While traversing, if we encounter a node already in the set, we’ve found a cycle.
- If we reach
null, there’s no cycle.
Time and Space Complexity:
- Time Complexity: O(n), where n is the number of nodes in the list.
- Space Complexity: O(n), in the worst case we store all nodes in a set.
var hasCycle = function(head) {
let seenNodes = new Set();
let curr = head;
while (curr !== null) {
if (seenNodes.has(curr)) {
return true;
}
seenNodes.add(curr);
curr = curr.next;
}
return false;
};
class Solution(object):
def hasCycle(self, head):
seen = set()
while head:
if head in seen:
return True
seen.add(head)
head = head.next
return False
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> seen = new HashSet<>();
while (head != null) {
if (seen.contains(head)) {
return true;
}
seen.add(head);
head = head.next;
}
return false;
}
}
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> seen;
while (head != nullptr) {
if (seen.count(head)) return true;
seen.insert(head);
head = head->next;
}
return false;
}
};
bool hasCycle(struct ListNode *head) {
struct ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
public class Solution {
public bool HasCycle(ListNode head) {
HashSet<ListNode> seen = new HashSet<ListNode>();
while (head != null) {
if (seen.Contains(head)) {
return true;
}
seen.Add(head);
head = head.next;
}
return false;
}
}
