Linked List Cycle
Detect whether a linked list contains a cycle.
Progress cannot be saved in this browser, so completed lessons will reset when you leave.
Lesson notes
Try it before you watch
Restate the problem in your own words, list the edge cases, and sketch a solution with its running time. Then play the video and compare.
Reveal the key idea
Floyd's tortoise and hare: a slow pointer moves one step and a fast pointer two. They meet if and only if there is a cycle.
Pattern: Linked lists. Re-wire next pointers carefully; a dummy head and fast/slow pointers remove most edge cases.
Complexity
| Measure | Bound |
|---|---|
| Time | O(n) |
| Extra space | O(1) |
Walkthroughs often start from a simpler approach first; aim to reach these bounds. New to Big-O? Read understanding algorithmic complexity.