141. Linked List Cycle
## description
## 141. Linked List Cycle
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
1Input: head = [3,2,0,-4], pos = 1
2Output: true
3Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).Example 2:
1Input: head = [1,2], pos = 0
2Output: true
3Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.Example 3:
1Input: head = [1], pos = -1
2Output: false
3Explanation: There is no cycle in the linked list.Constraints:
- –The number of the nodes in the list is in the range [0, 104].
- –-105 <= Node.val <= 105
- –pos is -1 or a valid index in the linked-list.
Follow up: Can you solve it using O(1) (i.e. constant) memory?
## notes
### Intuition
Floyd's cycle detection uses two pointers moving at different speeds. If there's a cycle, the fast pointer will eventually lap the slow pointer and they'll meet. If there's no cycle, the fast pointer will reach the end.
### Implementation
Initialize both slow and fast pointers to the head. Iterate while fast and fast.next exist. Move slow by one step and fast by two steps. After each move, check if they're equal—if so, a cycle exists. If the loop terminates (fast reaches null), there's no cycle.
### Edge-cases
The iteration condition fast and fast.next naturally handles empty lists and lists with a single node.
- –Time: O(n) — fast pointer traverses at most 2n nodes before meeting slow
- –Space: O(1) — only two pointers
### Complexity
## solution
1from typing import Optional
2from lcutils import ListNode
3
4# Definition for singly-linked list.
5# class ListNode:
6# def __init__(self, x):
7# self.val = x
8# self.next = None
9
10class Solution:
11 def hasCycle(self, head: Optional[ListNode]) -> bool:
12 slow = head
13 fast = head
14 while slow and fast and fast.next:
15 slow = slow.next
16 fast = fast.next.next
17 if fast == slow:
18 return True
19 return False
20
21
22
23
24if __name__ == "__main__":
25 # Include one-off tests here or debugging logic that can be run by running this file
26 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
27 solution = Solution()
28