A cycle or loop in a singly-linked list occurs when a node in the list points back to a previous node, creating a closed loop. This means that by continuously following the next pointers, you will eventually revisit the same node, rather than reaching the end of the list (which would normally be indicated by a NULL pointer).
Key Points:
Definition: A cycle in a linked list exists if there is some node in the list that can be reached again by continuously following the next pointer[2][3][7].
Detection Methods:
Hashing/Map Approach: Traverse the linked list and store each visited node in a hash table or map. If a node is encountered that is already in the hash table, a cycle is detected[1][5][9].
Two Pointers (Floyd’s Cycle Detection Algorithm): Use two pointers, slow and fast. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle, the fast pointer will eventually meet the slow pointer[4][7][9].
Example:
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)[2].
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[2].
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list[2].
Code Examples:
Using Hashing:
def has_cycle(head):
visited = set()
current = head
while current:
if current in visited:
return True
visited.add(current)
current = current.next
return False
