Linked Lists: Detect a Cycle
Category: Linked Lists
Difficulty: Easy
Determine whether a given linked list has a cycle.
Input: the head of a linked list with
struct Node {
int data;
struct Node* next;
}
Output: true
if the list has a cycle and false
if it terminates.
One way to detect a cycle in the linked list is to iterate over the list and use a set to mark each node as visited. If you reach a node that has already been added to the set, there is a cycle. The list terminates if and only if there is no cycle.
Another way to detect a cycle comes from Floyd's Tortoise and Hare: use two pointers to read through the
list, where one pointer iterates sequentially (
If you think about lists with different lengths and different cycle lengths, it
may not be obvious that this is always true. Assume that the list of
Many other approaches are viable to solve this problem. Notice that the list has at most 100 nodes. If you iterate over 100 nodes in the list and still haven't found the end, there must have been a cycle.
Java 7:
boolean hasCycle(Node head) {
Set<Node> nodes = new HashSet<>();
Node current = head;
while (current != null) {
if (nodes.contains(current)) {
return true;
}
nodes.add(current);
current = current.next;
}
return false;
}
C++:
bool has_cycle(Node* head) {
if (!head) {
return false;
}
Node* current = head;
Node* next = current->next;
while (current != next) {
if (!next || !next->next) {
return false;
}
current = current->next;
next = next->next->next;
}
return true;
}
Python 3:
def has_cycle(head):
nodes = set()
current = head
while current:
if current in nodes:
return True
nodes.add(current)
current = current.next
return False
Alternate Python 3 Solution:
def has_cycle(head):
MAX_NODES = 100
node_count = 0
current = head
while current and node_count <= MAX_NODES:
node_count += 1
current = current.next
return node_count > MAX_NODES