Unit 6 Session 1 (Click for link to problem statements)
TIP102 Unit 5 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
False
as there is no cycle.HAPPY CASE
Input: head = Node(1, Node(2, Node(3, Node(1))))
Output: True
Explanation: The last node points back to the first node, creating a cycle.
EDGE CASE
Input: head = None
Output: False
Explanation: An empty list cannot contain a cycle.
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
This problem is a classic example of detecting cycles in a linked list, typically solved using the Floyd's Tortoise and Hare algorithm, which uses two pointers moving at different speeds.
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Utilize two pointers, one slow and one fast, to traverse the list. If the fast pointer ever equals the slow pointer, a cycle is present.
1) Initialize two pointers, both at the head of the list.
2) Move the slow pointer by one step and the fast pointer by two steps in each iteration.
3) If the fast pointer either becomes null or reaches the end of the list, return `False`.
4) If the slow pointer ever meets the fast pointer, return `True`.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # move slow pointer by 1 step
fast = fast.next.next # move fast pointer by 2 steps
if slow == fast:
return True # Cycle detected
return False # No cycle detected
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume n
represents the number of nodes in the linked list.
O(n)
because, in the worst-case scenario, the fast pointer might need to travel around the entire list once before meeting the slow pointer, assuming there is a cycle.O(1)
because no additional space is used regardless of the size of the input list.