Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: head = [3,2,0,-4], pos = 1
Output: 1
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Input: head = [1,2], pos = 0
Output: 0
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
EDGE CASE
Input: head = [1], pos = -1
Output: -1
Explanation: There is no cycle in the linked list.
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.
For Linked List problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: First detect whether or not a cycle exist. Second determine the location of the cycle.
1. Detect Cycle
a. Instantiate two pointers where slow points to the head of the list and fast points to head
b. Move slow once and fast twice until they meet
c. If fast or fast.next is None then we have reached the end of cycle and return None
2. Determine the distance between head node and slow.
a. Lets say H: is distance from head to cycle entry E slow is currently H + D
b. Lets say D: is the distance from E to X
c. Lets say X: is the location slow meets fast
d. Lets say L: cycle length
_____
/ \
head_____H______E \
\ /
X_____/
e. When slow catches fast, slow traveled H + D and fast traveled 2(H + D)
f. Assume fast traveled n loops in cycle
- 2H + 2D = H + D + L
- H + D = nL
- H = nl - D
g. Therefore if two pointers start from head and the other from X, both reaches E at the same time, because slow and fast met at -D.
3. Shift head node and E until they meet and return
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Instantiate two pointers where slow and fast points to the head of the list
slow = fast = head
# Move slow once and fast twice until they meet
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
# If fast or fast.next is None then we have reached the end of cycle and return None
if not fast or not fast.next:
return None
# Find the distance from H to point of entry to cycle using theory(see above)
# Shift head node and E until they meet and return
e = slow
h = head
while e.next:
if e == h:
return e
e = e.next
h = h.next
public class Solution {
public ListNode detectCycle(ListNode head) {
// Instantiate two pointers where slow and fast points to the head of the list
ListNode slow = head, fast = head;
// Move slow once and fast twice until they meet
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
// If fast or fast.next is None then we have reached the end of cycle and return None
if (fast == null || fast.next == null) return null;
// Find the distance from H to point of entry to cycle using theory(see above)
while (head != slow) {
head = head.next;
slow = slow.next;
}
return head;
}
}
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 we may need to traverse all nodes in the linked list at least twice. O(1)
because we only need a few pointers for memory.