Sign in
Skip to solution
mediumDSA

How do you find the node where a linked list cycle begins?

607 views
01

Understand the problem

Explain Floyd's phase two.

linked-listcycle
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

First detect the cycle with Floyd's slow/fast pointers. Then reset one pointer to the head and advance both one step at a time — they meet at the cycle's start. This works because of the equal-distance property from the meeting point. O(n), O(1).

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Floyd two-phase
Run Playground
class ListNode:
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:           # phase 1: detect
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head                 # phase 2: locate
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None


# --- demo ---  1->2->3->4->5 with tail looping back to node 2
n1, n2, n3, n4, n5 = ListNode(1), ListNode(2), ListNode(3), ListNode(4), ListNode(5)
n1.next, n2.next, n3.next, n4.next, n5.next = n2, n3, n4, n5, n2  # cycle
start = detect_cycle(n1)
print(start.val if start else None)   # 2
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 63 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track