Hot100: Linked List Cycle II Floyd Detection + Entry Localization ACERS Guide

Subtitle / Summary
LeetCode 142 upgrades cycle detection into cycle entry localization. The robust template is Floyd: first detect a meeting inside the cycle, then reset one pointer to head and move both by one step; the next meeting node is the cycle entry.

Reading time: 12-16 min
Tags: Hot100, linked list, fast slow pointers, Floyd
SEO keywords: Linked List Cycle II, cycle entry, Floyd, fast slow pointers, O(1) space, LeetCode 142, Hot100
Meta description: Floyd cycle detection + entry localization with proof intuition, engineering mapping, and runnable multi-language implementations in O(n) time and O(1) extra space.

A - Algorithm (Problem and Algorithm)

Problem Restatement

Given head of a singly linked list, return the node where the cycle begins. If there is no cycle, return null.

Notes:

pos in the statement is only for test-data construction
pos is not a function argument
list structure must not be modified

Input / Output

Name	Type	Description
head	ListNode	head of singly linked list
return	ListNode / null	entry node reference, or null

Example 1

head: 3 -> 2 -> 0 -> -4
           ^         |
           |_________|

output: node(2)

Example 2

head: 1 -> 2 -> 3 -> null
output: null

Target Readers

Hot100 learners who want to fully internalize the 141 -> 142 linked-list template family
Developers who need to locate where a pointer chain becomes cyclic
Interview candidates who want to explain why “reset to head” works

Background / Motivation

In real systems, cycle corruption in chain structures can cause:

endless traversal loops
stuck cleanup tasks
misleadingly stable but non-progressing runtime behavior

Detecting whether a cycle exists is helpful, but operations/debugging usually require more:

where does the cycle begin?

That exact requirement is modeled by LeetCode 142.

Core Concepts

Concept	Meaning	Why it matters
Cycle	Following `next` eventually revisits a node	causes non-terminating traversals
Entry node	First node where linear prefix enters the loop	required return value
Floyd algorithm	`slow` moves 1 step, `fast` moves 2 steps	O(1) extra memory
Meeting point	First collision inside cycle	bridge to entry localization
Identity equality	compare node reference, not node value	value duplicates are common

C - Concepts (Core Ideas)

How To Build The Solution From Scratch

Step 1: Start from the smallest picture that separates “has cycle” from “where is the entry”

Imagine:

head -> a -> b -> c -> d
              ^         |
              |_________|

Here:

the list does have a cycle
the answer is specifically node b

So LeetCode 142 is stricter than LeetCode 141. Detection alone is not enough; we need the first node where the linear prefix enters the loop.

Step 2: Ask what the most direct correct solution would remember

The simplest approach is:

traverse node by node
store each node reference in a set
the first repeated node is the entry

This is easy to reason about, but it costs O(n) extra space. The problem becomes interesting only when we try to keep memory at O(1).

Step 3: Reuse Floyd for phase 1 and define when the work is settled

With Floyd:

slow moves 1 step
fast moves 2 steps

Then exactly one of two things happens:

fast reaches null or fast.next reaches null, so there is no cycle
slow and fast meet inside the cycle

That meeting gives us more than a boolean result: it gives us a concrete node already inside the loop.

Step 4: Ask what information the meeting point gives us

Suppose:

a = distance from head to cycle entry
b = distance from cycle entry to first meeting point
c = cycle length

At the first meeting:

slow traveled a + b
fast traveled 2(a + b)

Their distance difference must be whole cycle lengths:

2(a + b) - (a + b) = k * c
=> a + b = k * c
=> a = k * c - b

This means:

from head to entry: a steps
from meeting point to entry: also a steps modulo the cycle

That is the hidden structure we need for localization.

Step 5: Turn the math into a second pointer phase

Once slow meets fast, keep one pointer at that meeting node and reset the other to head:

p1 = head
p2 = slow

Now move both one step at a time. Because both are exactly a steps away from the entry in the modular sense, their next meeting point must be the entry.

Step 6: Walk one concrete trace

Take:

3 -> 2 -> 0 -> -4
     ^         |
     |_________|

The entry is node 2. Floyd first meets somewhere inside the cycle, not necessarily at 2. But after resetting one pointer to head and moving both one step at a time, they align at 2.

That is why the algorithm returns the entry instead of an arbitrary cycle node.

Step 7: Reduce the method to one sentence

LeetCode 142 is “use Floyd to get one guaranteed node inside the cycle, then align head and meeting point to walk into the entry together.”

Assemble the Full Code

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def detect_cycle(head: Optional[ListNode]) -> Optional[ListNode]:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            p1 = head
            p2 = slow
            while p1 is not p2:
                p1 = p1.next
                p2 = p2.next
            return p1
    return None

Reference Answer

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def detect_cycle(head: Optional[ListNode]) -> Optional[ListNode]:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            p1 = head
            p2 = slow
            while p1 is not p2:
                p1 = p1.next
                p2 = p2.next
            return p1
    return None

Method Category

Two pointers (fast/slow)
Floyd cycle detection
Distance alignment after reset

Why reset-to-head works

Define:

a: distance from head to cycle entry
b: distance from entry to first meeting point
c: cycle length

At first meeting:

slow traveled a + b
fast traveled 2(a + b)

Difference is one whole number of cycle lengths:

2(a + b) - (a + b) = k * c
=> a + b = k * c
=> a = k * c - b

Meaning:

from head to entry: a steps
from meeting point to entry: also a steps modulo cycle length

So moving one pointer from head and one from meeting, both one step each round, guarantees meeting at the entry.

Invariant for localization phase

During phase 2, both pointers have equal remaining distance (modulo cycle) to entry. Equal-speed synchronous movement preserves this equality, so collision point is entry.

Practical Guide / Steps

Initialize slow = head, fast = head
Detection loop:
- slow = slow.next
- fast = fast.next.next
- if pointers meet, break
If fast == null or fast.next == null, no cycle -> return null
Set p1 = head, p2 = meeting
Move both by one step until p1 == p2
Return p1 (entry)

Runnable Example (Python)

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def detect_cycle(head: Optional[ListNode]) -> Optional[ListNode]:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            p1 = head
            p2 = slow
            while p1 is not p2:
                p1 = p1.next
                p2 = p2.next
            return p1
    return None


def build_cycle_list(values, pos):
    dummy = ListNode()
    tail = dummy
    entry = None
    for idx, x in enumerate(values):
        tail.next = ListNode(x)
        tail = tail.next
        if idx == pos:
            entry = tail
    if tail and pos >= 0:
        tail.next = entry
    return dummy.next


if __name__ == "__main__":
    h = build_cycle_list([3, 2, 0, -4], 1)
    e = detect_cycle(h)
    print(e.val if e else None)  # 2

Explanation / Why This Works

The algorithm is split by responsibility:

phase 1 answers: cycle or no cycle
phase 2 answers: where cycle starts

This separation is important for correctness and debugging.

Setting one pointer to head is not a trick; it is distance alignment derived from meeting-point equations. That is why this method is both memory-optimal and proof-friendly.

E - Engineering (Real-world Scenarios)

Scenario 1: asynchronous callback chain corruption check (Go)

Background: callback chain unexpectedly loops in production.
Why it fits: no extra map allocation, works on large chains.

package main

type Node struct {
	Val  int
	Next *Node
}

func detectCycle(head *Node) *Node {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			p1, p2 := head, slow
			for p1 != p2 {
				p1 = p1.Next
				p2 = p2.Next
			}
			return p1
		}
	}
	return nil
}

Scenario 2: ETL pointer-chain anomaly localization (Python)

Background: transformed record chain can accidentally self-link.
Why it fits: allows locating the first bad join node directly.

# Reuse detect_cycle(head) above and log entry node identity/value.

Scenario 3: front-end linked-state graph guard (JavaScript)

Background: linked state nodes in memory may form unintended cycles. Why it fits: fast runtime check in debug tooling.

function detectCycle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      let p1 = head;
      let p2 = slow;
      while (p1 !== p2) {
        p1 = p1.next;
        p2 = p2.next;
      }
      return p1;
    }
  }
  return null;
}

R - Reflection

Complexity

Time: O(n)
Extra space: O(1)

Alternatives and Tradeoffs

Method	Time	Space	Notes
visited hash set	O(n)	O(n)	easy, but extra memory
Floyd + reset	O(n)	O(1)	optimal for constraints

Common Mistakes

forgetting fast && fast.next null checks
comparing node values (val) instead of references
returning meeting point directly (meeting is not always entry)
modifying list to mark visited nodes (forbidden by problem)

Why this method is optimal in practice

no structural mutation
no extra memory pressure
deterministic behavior under large lists
strong proof story for interviews and code review

FAQ and Notes

Why is the first meeting point not necessarily the entry?
Because fast and slow can first collide anywhere inside the cycle.
Can this fail with duplicate values?
No, if you compare references (is, == pointer) rather than values.
What if list length is very small?
Null checks naturally handle 0 or 1 node lists.
Can we stop once cycle is detected?
For LeetCode 141 yes; for 142 you must run localization phase.

Best Practices

Implement 141 and 142 as a pair to reuse mental model
Keep phase separation explicit in code (detect then locate)
Add tests for:
- no cycle
- single-node self-cycle
- cycle entry at head
- cycle entry in middle
In production debug tools, print entry node identity and predecessor info when possible

S - Summary

LeetCode 142 extends cycle detection to entry localization
Floyd detects cycle with O(1) memory
Reset-to-head works by distance alignment, not memorized magic
Correct implementation depends on reference comparison and null-safe traversal
This pattern is reusable for many chain-integrity diagnostics

Recommended Follow-up

LeetCode 141 — Linked List Cycle
LeetCode 160 — Intersection of Two Linked Lists
Floyd cycle-finding notes in pointer-heavy systems
General linked-list invariants and mutation safety patterns

Conclusion

Once you understand “detect first, then reset and align distances”, Linked List Cycle II becomes a stable template rather than a memorized trick.

References

Meta Info

Reading time: 12-16 min
Tags: Hot100, linked list, fast/slow pointers, Floyd
SEO keywords: Linked List Cycle II, cycle entry, Floyd, LeetCode 142
Meta description: O(n)/O(1) cycle entry localization with Floyd fast/slow pointers and reset alignment proof.

Call To Action (CTA)

Run this mini drill:

Re-implement 141 and 142 back-to-back from memory
Write the distance equation once (a+b = k*c) and explain it aloud
Build four edge-case tests and verify pointer identity-based assertions

Multi-language Implementations (Python / C / C++ / Go / Rust / JS)

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def detect_cycle(head: Optional[ListNode]) -> Optional[ListNode]:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            p1 = head
            p2 = slow
            while p1 is not p2:
                p1 = p1.next
                p2 = p2.next
            return p1
    return None

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *slow = head;
    struct ListNode *fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            struct ListNode *p1 = head;
            struct ListNode *p2 = slow;
            while (p1 != p2) {
                p1 = p1->next;
                p2 = p2->next;
            }
            return p1;
        }
    }
    return NULL;
}

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                ListNode *p1 = head;
                ListNode *p2 = slow;
                while (p1 != p2) {
                    p1 = p1->next;
                    p2 = p2->next;
                }
                return p1;
            }
        }
        return nullptr;
    }
};

func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            p1, p2 := head, slow
            for p1 != p2 {
                p1 = p1.Next
                p2 = p2.Next
            }
            return p1
        }
    }
    return nil
}

use std::cell::RefCell;
use std::rc::Rc;

type Link = Option<Rc<RefCell<ListNode>>>;

#[derive(Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Link,
}

pub fn detect_cycle(head: Link) -> Link {
    let mut slow = head.clone();
    let mut fast = head.clone();

    loop {
        slow = match slow.clone() {
            Some(node) => node.borrow().next.clone(),
            None => return None,
        };

        fast = match fast.clone() {
            Some(node) => match node.borrow().next.clone() {
                Some(next1) => next1.borrow().next.clone(),
                None => return None,
            },
            None => return None,
        };

        match (slow.clone(), fast.clone()) {
            (Some(s), Some(f)) if Rc::ptr_eq(&s, &f) => break,
            (Some(_), Some(_)) => {}
            _ => return None,
        }
    }

    let mut p1 = head;
    let mut p2 = slow;
    loop {
        match (p1.clone(), p2.clone()) {
            (Some(a), Some(b)) => {
                if Rc::ptr_eq(&a, &b) {
                    return Some(a);
                }
                p1 = a.borrow().next.clone();
                p2 = b.borrow().next.clone();
            }
            _ => return None,
        }
    }
}

function detectCycle(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      let p1 = head;
      let p2 = slow;
      while (p1 !== p2) {
        p1 = p1.next;
        p2 = p2.next;
      }
      return p1;
    }
  }
  return null;
}

A - Algorithm (Problem and Algorithm)#

Problem Restatement#

Input / Output#

Example 1#

Example 2#

Target Readers#

Background / Motivation#

Core Concepts#

C - Concepts (Core Ideas)#

How To Build The Solution From Scratch#

Step 1: Start from the smallest picture that separates “has cycle” from “where is the entry”#

Step 2: Ask what the most direct correct solution would remember#

Step 3: Reuse Floyd for phase 1 and define when the work is settled#

Step 4: Ask what information the meeting point gives us#

Step 5: Turn the math into a second pointer phase#

Step 6: Walk one concrete trace#

Step 7: Reduce the method to one sentence#

Assemble the Full Code#

Reference Answer#

Method Category#

Why reset-to-head works#

Invariant for localization phase#

Practical Guide / Steps#

Runnable Example (Python)#

Explanation / Why This Works#

E - Engineering (Real-world Scenarios)#

Scenario 1: asynchronous callback chain corruption check (Go)#

Scenario 2: ETL pointer-chain anomaly localization (Python)#

Scenario 3: front-end linked-state graph guard (JavaScript)#

R - Reflection#

Complexity#

Alternatives and Tradeoffs#

Common Mistakes#

Why this method is optimal in practice#

FAQ and Notes#

Best Practices#

S - Summary#

Recommended Follow-up#

Conclusion#

References#

Meta Info#

Call To Action (CTA)#

Multi-language Implementations (Python / C / C++ / Go / Rust / JS)#