Linked List Cycle

Learning goal: Recognize when a linked-list traversal contains a loop and why revisiting a node matters.

Core idea A normal singly linked list eventually reaches null. A cyclic list never does: its next pointers repeatedly send traversal through nodes that were already visited. The task is to detect that structural behavior, not merely to find duplicate values, because two different nodes may contain the same value.

Algorithm plan

• Start two references at the head: slow and fast.
• Move slow one link at a time.
• Move fast two links at a time.
• Report a cycle if the references become identical.
• Report no cycle if fast or fast.next is null.

Micro-example For 3 → 2 → 0 → -4 → 2, the final arrow returns to the node containing 2. For 1 → 2 → null, every traversal eventually stops.

Pitfalls

• Compare node identity, not node values.
• An empty list has no cycle.
• A single node pointing to itself is still a cycle.

Recap

• Cycles are about repeated nodes, not repeated values.
• Termination at null proves that no cycle exists.
• Floyd's method detects both outcomes with two moving references.

Learning goal: Understand why a fast pointer must meet a slow pointer exactly when a loop exists.

Core idea Imagine the list as a straight path leading into a circular track. Before entering the track, both pointers move forward. Once both are on the circular portion, fast gains one node per round on slow, so it eventually laps and meets it. If there is no circular portion, fast simply reaches the end first.

Data structure model

• slow advances by slow = slow.next.
• fast advances by fast = fast.next.next.
• The test is made after both have advanced.
• Before taking two steps, verify fast !== null and fast.next !== null.

Micro-example In 3 → 2 → 0 → -4 → 2, after a few rounds the pointers occupy the same -4 node. In 1 → 2 → null, fast.next is eventually null, so the loop stops safely.

Pitfalls

• Checking pointer identity before the first movement can misclassify slow === fast at the head.
• Moving fast twice without guarding fast.next can dereference null.
• The speed difference is one node per iteration, which is what guarantees a meeting.

Recap

• A loop turns the suffix into a circular track.
• fast laps slow if and only if that track exists.
• The null guard protects the two-step movement.

Learning goal: Translate the pointer race into a safe, implementation-ready algorithm.

Core idea Initialize both references at the head, then perform a guarded movement loop. The guard is evaluated before fast.next.next, because fast may already be null or may point to the final node. After each complete movement, pointer identity is checked. A meeting is conclusive evidence of a cycle because two traversals starting at the same head can only occupy the same node after different progress if the structure loops.

Algorithm plan

slow = head
fast = head
while fast is not null and fast.next is not null:
    slow = slow.next
    fast = fast.next.next
    if slow is fast:
        return true
return false

Micro-example For the cycle 3 → 2 → 0 → -4 → 2, both pointers enter the loop and eventually coincide.

Pitfalls

• The loop guard belongs before the two-step assignment.
• Use reference identity, such as slow === fast.
• Do not allocate a set of visited nodes if constant space is required.

Recap

• Guard, advance both, then compare.
• A meeting proves a loop; a null guard proves termination.
• The method uses constant auxiliary space.

Learning goal: Trace every pointer movement on the example 3 → 2 → 0 → -4 → 2.

Core idea The tail does not point to a new node; it points back to the node containing 2. We will label nodes by identity so the repeated destination is visible. Both pointers begin at the head, but we do not declare a cycle merely because they initially share that node. Instead, each round advances slow once and fast twice, then checks whether they meet.

Data structure model

• n1 stores 3 and points to n2.
• n2 stores 2 and points to n3.
• n3 stores 0 and points to n4.
• n4 stores -4 and points back to n2.
• The cycle is n2 → n3 → n4 → n2.

Micro-example Round 1: slow reaches n2; fast reaches n3. Round 2: slow reaches n3; fast reaches n2. Round 3: both reach n4, so the references are identical.

Pitfalls

• n2 appears again as a destination, but it is one stable node, not a copied value.
• fast must take two valid links at every round.
• The meeting can happen anywhere inside the loop, not necessarily at its entry.

Recap

• The visualization tracks node IDs and pointer positions.
• The pointers meet at n4 after advancing.
• That meeting returns true.

Learning goal: Prevent the two implementation mistakes that most often break cycle detection.

Core idea The safest loop structure checks whether two steps are available before moving fast. It then advances both pointers and compares their identities. This ordering handles empty lists, one-node lists, and ordinary terminating lists without special-case code.

Algorithm plan

• Empty list: head is null, so the loop never starts and the answer is false.
• One node to null: fast.next is null, so the answer is false.
• One node to itself: both pointers move back to that same node, so the answer is true.
• Any longer cycle: continue until the references meet.

Micro-example For 1 → 2 → null, the initial guard fails because fast.next eventually becomes null. For 7 → 7, the self-link makes the pointers meet after a movement.

Pitfalls

• Do not compare val fields.
• Do not forget that head = null is valid.
• Do not use a visited set when the target space is O(1).

Recap

• Guard before the two-step move.
• Compare after advancing.
• Identity, not value equality, determines a meeting.

Learning goal: Explain why Floyd's method meets the target complexity and summarize the reusable pattern.

Core idea The pointers may traverse a short non-cyclic prefix and then move around a cycle. Each movement advances through an existing node, and the fast pointer either reaches null or catches the slow pointer after a linear number of steps. The algorithm stores only two references, so its auxiliary memory does not grow with the list size.

Algorithm plan

• Maintain slow and fast only.
• Spend constant work per loop iteration.
• Stop on either a guarded null condition or pointer identity equality.
• Return the corresponding Boolean result.

Micro-example The walkthrough visits a constant number of pointer states for its four-node structure. For a list with n nodes, the same process scales linearly rather than storing all n identities.

Pitfalls

• A visited-set solution is correct but uses O(n) extra space.
• Big-O counts nodes and pointer operations, not the numeric values stored in nodes.
• The method detects existence; finding the cycle entry requires a second Floyd phase.

Recap

• Time complexity: O(n).
• Auxiliary space: O(1).
• Fast laps slow if and only if a loop is reachable.
• The reusable pattern is a speed difference plus a guarded identity check.