Can YOU escape this infinite cycle? (Most can't.)
Amazing and clever algorithm that's almost impossible to figure out for yourself, but unforgettable once you've seen it. This video introduces Floyd's Cycle finding algorithm for singly linked lists. It's a common data structures and algorithms (DSA) interview question at big companies like Google, Microsoft, Amazon, or Meta. I also cover a simpler approach using sets that is not O(1) for memory usage but can sometimes be faster.
Both approaches are answers for Leetcode problem 141, Linked List Cycle. It is a difficult question to figure out on your own, but this gentle introduction to finding linked list cycles is suitable for anybody who has written a little code before.
Here are my code solutions for Python and Java. If you can solve the problem of finding cycles in a singly linked list in another language, post it below!
If you like my teaching style, I offer private tutoring:
https://www.codeslatetutoring.com/fro...
Leetcode 141 problem description:
https://leetcode.com/problems/linked-...
Basic Python solution (beats 93% for speed and memory):
Standard Floyd's Cycle Detection, as shown in video:
class Solution:
def hasCycle(self, head: Optional[ListNode]):
Edge case: 0 or 1 items in list. This cannot contain a cycle, so return false.
if head is None or head.next is None:
return False
fast, slow = head, head
while fast != None and fast.next != None:
fast = fast.next.next # Move fast forward twice
slow = slow.next # Move slow forward once
if fast == slow:
return True
If we exit the loop, it means fast hit a None and hence, we never got
trapped in a cycle.
return False
My Java solution (beats 100% for speed OR 99% for memory):
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
ListNode slow = head;
while(head != null && head.next!= null){
head = head.next.next;
slow = slow.next;
if(head == slow){
//uncomment next line for better score on memory, but speed suffers
//System.gc();
return true;
}
}
//uncomment next line for better score on memory, but speed suffers
// System.gc();
return false;
}
}