Linked List Cycle
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Decide whether a linked list loops back on itself.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Remembering every visited node works but uses memory. Can you detect a loop with two moving markers?
- Hint 2If one marker moves faster than the other, what happens inside a loop?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Two runners start on a track. The tortoise takes one step at a time, the hare takes two. If the track is a straight road, the hare simply reaches the end. If the track is a circle, the hare keeps going round and sooner or later runs into the tortoise from behind. Meeting means a loop; reaching the end means none.
- The obvious way
Store every visited node in a set and see if you meet one again: O(n) memory.
- The key insight
Move a slow marker one step and a fast marker two steps. With no loop the fast marker falls off the end. With a loop both end up circling inside it, and the fast one gains one step on the slow one each round, so they must land on the same node.
- The algorithm
- Both markers start at the head.
- Each round: slow moves 1 step, fast moves 2 steps.
- Fast fell off the end (nothing ahead)? No loop: answer False.
- Fast and slow are on the same node? Loop: answer True.
Watch it run
Examplelist: 3 -> 2 -> 0 -> -4, and -4 points back to 2
Both start at 3. Slow steps to 2, fast steps two to 0.
slow at 2, fast at 0
Where people slip
- Check both fast and fast.next before taking two steps, or you will crash at the end.
- Compare nodes (identity), not their values: values can repeat.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
# ListNode is provided
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # tortoise: one step
fast = fast.next.next # hare: two steps
if slow is fast:
return True # the hare caught the tortoise
return FalseNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.