Sign in
Skip to solution
mediumDSA

How do you detect a cycle in a linked list?

474 views
01

Understand the problem

Explain Floyd's algorithm.

linked-listpointers
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Use Floyd's tortoise and hare: advance a slow pointer one step and a fast pointer two steps. If they ever meet, there's a cycle; if fast reaches null, there isn't. It runs in O(n) time and O(1) space.

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Floyd's cycle detection
Run Playground
class ListNode:
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False


# --- demo ---
a, b, c, d = ListNode(1), ListNode(2), ListNode(3), ListNode(4)
a.next, b.next, c.next, d.next = b, c, d, b   # tail links back -> cycle
print(has_cycle(a))                            # True
x = ListNode(1); x.next = ListNode(2)
print(has_cycle(x))                            # False
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 71 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track