141. Linked List Cycle
Model: qwen2.5-coder:14b
Topics: Linked List,Two Pointers
FAANG asked: 1
Acceptance rate: 43.1%
Problem Breakdown
The problem asks us to determine if there is a cycle in a singly linked list given its head node. A cycle exists if following the next pointers from any node eventually leads back to that same node.
Inputs:
head: The head node of the linked list.
Outputs:
- Return
trueif there is a cycle in the linked list; otherwise, returnfalse.
Implicit Constraints or Tricky Edge Cases:
- An empty linked list (i.e.,
headisnull) should returnfalse. - The list could have only one node without a cycle.
- The list could be very long, so the solution should be efficient in terms of both time and space.
Intuition
A brute-force approach would involve using a hash set to keep track of visited nodes. As we traverse the linked list, we add each node to the set. If we encounter a node that is already in the set, we have detected a cycle. However, this approach requires O(n) space complexity due to the storage of node references.
A more efficient approach involves using two pointers, often referred to as the “tortoise and the hare” algorithm. The idea is to use two pointers, one moving twice as fast as the other. If there is a cycle, the faster pointer will eventually meet the slower pointer inside the cycle. This approach only requires O(1) space.
Approach
We will use the two-pointer technique:
- Initialize two pointers,
slowandfast. Both start at the head of the linked list. - Move
slowone step at a time (slow = slow.next) andfasttwo steps at a time (fast = fast.next.next). - If there is no cycle,
fastwill eventually reach the end of the list (null), and we returnfalse. - If there is a cycle,
fastwill eventually meetslowinside the cycle, and we returntrue.
Complexity Analysis
- Time Complexity:
O(n), wherenis the number of nodes in the linked list. In the worst case, both pointers traverse the entire list once. - Space Complexity:
O(1). We only use a constant amount of extra space for the two pointers.
Solution
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def hasCycle(head: ListNode) -> bool:
if not head or not head.next:
return False
slow = head
fast = head.next
while slow != fast:
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return True
Edge Cases Handled
- Empty List: If the list is empty (
headisnull), the function returnsfalse. - Single Node List: If the list has only one node and no cycle, the function returns
false. - Cycle at the Start: The algorithm correctly identifies cycles where the tail connects back to the head.
- Cycle in the Middle: The algorithm correctly identifies cycles that occur anywhere other than the start of the list.