Linked List Cycle II — Editorial

Opening the reading…

Intuitionwhy one meeting point is enough to locate the entrance

A singly linked list without a cycle eventually reaches null. With a cycle, every pointer that enters the cycle keeps moving around the same ring. Let the path from head to the cycle start have length a, let the cycle length be c, and let the meeting point be b steps around the cycle from its start. The slow pointer has travelled a + b steps when the two pointers meet.

The fast pointer has travelled twice as far, so the extra distance is also a whole number of laps around the cycle. That makes the meeting point special: walking forward from it until the cycle start takes the same number of steps, modulo the cycle length, as walking from head to the cycle start. Reset one pointer to head and move both one step at a time; their first meeting is therefore the entrance.

The meeting point makes the second, one-step phase land exactly at the cycle entrance.

Approachtwo passes over pointer states, with no visited set

Handle head == nullptr and the one-node case immediately, because neither can provide a usable cycle entrance through a next pointer.

Start slow and fast at head. Move slow by one node and fast by two nodes while fast and fast->next exist, because those guards prevent dereferencing null when the list ends without a cycle.

When slow == fast, stop the detection phase rather than returning that node: the meeting proves that a cycle exists, but the meeting location is not generally its first node.

Reset slow to head and move slow and fast one node per iteration until they meet. The distance from head to the entrance equals the meeting point's forward distance to that entrance modulo the cycle length, so this second meeting identifies the answer.

Return the meeting node from the second phase. If the detection loop ends first, return nullptr because fast reached the end and no pointer can loop back.

Complexitythe cycle may be long, but each phase remains linear

MEASURE	BOUND	WHY
Time	O(n)	The detection phase advances through the non-cyclic prefix and at most a constant number of laps before the pointers meet; the reset phase advances at most the prefix length plus one cycle length. Both phases therefore visit O(n) pointer positions, without storing or revisiting an unbounded history.
Space	O(1)	Only the two pointer variables are used, and the returned node is output rather than working memory. The bound stays O(1) for an empty list, a long prefix, a one-node cycle, and every other input shape.

Here n is the number of nodes in the list. The returned node is required output and is excluded from extra space.

Annotated solutionC++ · Floyd's algorithm · detection followed by entrance recovery

CPPFloyd's two-pointer solution: detect a meeting, then align both pointers to find the cycle entrance.

#include <vector>
using namespace std;

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }

        ListNode* slow = head;
        ListNode* fast = head;

        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }

        return nullptr;
    }
};

The key placement is the reset inside the meeting branch. The first equality only establishes that both pointers are on the cycle. Moving slow back to head and then advancing both equally changes the comparison from 'where did the speeds coincide?' to 'where do the prefix distance and the remaining cycle distance coincide?' That is why the returned pointer is the entrance rather than an arbitrary cycle node.

The visited-set alternativesimpler identity tracking, at the cost of linear memory

A hash set gives a direct interpretation: walk one node at a time, and return the first node whose address has already appeared. This is not an optimisation; it trades O(1) extra space for a simpler invariant. It is reasonable when clarity matters more than memory, while Floyd's method is the required choice when constant extra space is important.

CPPA direct alternative that records node identity and returns the first repeated node.

#include <unordered_set>
using namespace std;

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        unordered_set<ListNode*> seen;

        ListNode* current = head;
        while (current != nullptr) {
            if (seen.count(current) != 0) {
                return current;
            }
            seen.insert(current);
            current = current->next;
        }

        return nullptr;
    }
};