LeetCode · #142

Linked List Cycle II Solution

Detect whether a cycle exists and return the node where the cycle begins. If no cycle exists, return null.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #142

🏗️

Pattern

Fast-slow pointers — Floyd's cycle entry

This is the follow-up to LC 141. Detecting a cycle is not enough anymore — we must recover the exact node where the loop begins, using only O(1) extra space.

Example

Input:  3 → 2 → 0 → -4 → (back to 2)
Output: node with value 2
// The cycle entry is the node where the tail reconnects.

Section Two · Approach 1

HashSet of Visited Nodes — O(n) Space

Walk the list, storing each node reference in a HashSet. The first node you encounter twice is exactly the cycle entry.

Problem: This works, but uses O(n) extra memory. The whole interview point is Floyd's algorithm: detect a cycle with two pointers, then recover the entry with a short mathematical trick and O(1) space.

Section Three · Approach 2

Floyd's Algorithm + Reset Pointer — O(1) Space

First run the standard slow/fast cycle detection. If they never meet, there is no cycle. If they do meet inside the loop, reset one pointer to head while keeping the other at the meeting point. Move both one step at a time. Their next meeting point is the cycle entry.

💡 Mental model: Imagine one runner starts again from the track entrance while the other stays at the meeting point inside the loop. They now run at equal speed. Because of how far the fast runner had already lapped the slow runner, the two distances line up exactly at the loop entrance.

Phase 1: detect whether a meeting happens.
If no meeting, return null.
Phase 2: set one pointer to head.
Move both pointers one step at a time.
The node where they meet is the cycle entry.

Why the reset works:

If the non-cycle prefix has length a and the cycle length is c, then when slow and fast first meet, the meeting point is exactly a steps away from the cycle entry when measured around the loop.
So one pointer from head and one from the meeting point reach the entry together.

Section Four · Trace

Visual Walkthrough

Trace 3 → 2 → 0 → -4 → (back to 2).

LC 142 — detect cycle, then recover entry

Section Five · Implementation

Code — Java & Python

Java — Floyd's entry-point recovery

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

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }

        return null;
    }
}

Python — detect meeting point, then reset

class Solution:
    def detectCycle(self, head: 'ListNode | None') -> 'ListNode | None':
        slow = fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                ptr = head
                while ptr != slow:
                    ptr = ptr.next
                    slow = slow.next
                return ptr

        return None

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
HashSet	O(n)	O(n)	Simple and direct, but not constant space.
Floyd's cycle entry ← optimal	O(n)	O(1)	Detects and locates the entry with two pointers only.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected behavior	Why it matters
No cycle	Return `null`	Fast pointer reaches the end.
Cycle starts at head	Return `head`	The reset logic must still work.
Single-node self-cycle	Return that node	Fast and slow meet immediately after one loop.
Meeting point ≠ entry	Still recover the entry	The first collision is usually inside the loop, not at the start.
Comparing node values	Wrong	Use node identity/reference equality, not `val`.

⚠ Common Mistake: After detecting the cycle, resetting both pointers to head. Only one pointer should reset to head; the other must stay at the meeting point. Then move both one step at a time until they meet at the entry.

← Back to Two Pointers problems

LearningTree

LC 142 · Linked List Cycle II — Solution & Explanation | DSA Guide