VietMX Staff asked 3 years ago
To detect if a list is cyclic, we can check whether a node had been visited before. A natural way is to use a hash table.
Algorithm
We go through each node one by one and record each node’s reference (or memory address) in a hash table. If the current node is null, we have reached the end of the list and it must not be cyclic. If current node’s reference is in the hash table, then return true.
Complexity Analysis
- Time complexity :
O(n). We visit each of thenelements in the list at most once. Adding a node to the hash table costs onlyO(1)time. - Space complexity:
O(n). The space depends on the number of elements added to the hash table, which contains at mostnelements.
Implementation
public boolean hasCycle(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}