Given the head node of a singly linked list, determine whether the linked list contains a cycle. A cycle exists if a node's next pointer eventually points back to a previous node in the list. Return True if a cycle exists, otherwise return False.
Example 1
Input: # Linked list: 5 -> 7 -> 9 -> 2 -> 7 (cycle at node with value 7) # Construction: n1 = ListNode(5) n2 = ListNode(7) n3 = ListNode(9) n4 = ListNode(2) n5 = ListNode(7) n1.next = n2 n2.next = n3 n3.next = n4 n4.next = n5 n5.next = n2 result = has_cycle(n1)
Output: True
Explanation: The last node points back to the second node, forming a cycle.
Example 2
Input: # Linked list: 10 -> 20 -> 30 -> 40 (no cycle) # Construction: n1 = ListNode(10) n2 = ListNode(20) n3 = ListNode(30) n4 = ListNode(40) n1.next = n2 n2.next = n3 n3.next = n4 result = has_cycle(n1)
Output: False
Explanation: No node points back to any previous node.
Example 3
Input: # Linked list: 1 (single node, no cycle) # Construction: n1 = ListNode(1) result = has_cycle(n1)
Output: False
Explanation: Single node with no cycle.
Constraints
Case 1
Input: # Linked list: 8 -> 6 -> 4 -> 2 -> 8 (cycle at node with value 8) n1 = ListNode(8) n2 = ListNode(6) n3 = ListNode(4) n4 = ListNode(2) n1.next = n2 n2.next = n3 n3.next = n4 n4.next = n1 result = has_cycle(n1)
Expected: True
Case 2
Input: # Linked list: 3 -> 5 -> 7 (no cycle) n1 = ListNode(3) n2 = ListNode(5) n3 = ListNode(7) n1.next = n2 n2.next = n3 result = has_cycle(n1)
Expected: False
Case 3
Input: # Linked list: empty result = has_cycle(None)
Expected: False
Case 4
Input: # Linked list: 11 -> 22 -> 33 -> 44 -> 22 (cycle at node with value 22) n1 = ListNode(11) n2 = ListNode(22) n3 = ListNode(33) n4 = ListNode(44) n1.next = n2 n2.next = n3 n3.next = n4 n4.next = n2 result = has_cycle(n1)
Expected: True