Description: Given head, the head of a linked list, determine if the linked list has a cycle in it.

Brute-force Approach

Iterate through the linked list, using a hashmap to store the visited nodes. If a node is visited again, there is a cycle.

Time: O(n)

Space: O(n)

Optimal Approach

Tortoise and Hare Algorithm: Use two pointers, one moving one step at a time and the second one moving two steps at a time. If there is a cycle, the two pointers will meet. If there is no cycle, the second (fast) pointer will reach the end of the list.

Time: O(n)

Space: O(1)