Linked List Cycle

Intuitionwhy a faster pointer must reveal a cycle

A singly linked list gives you only one direction to follow. If the next pointer eventually becomes null, a walk ends. If the list contains a cycle, the walk never ends because every node in the cycle points to another node in that same loop. The challenge is detecting repetition without storing every node you have visited.

Make one pointer move one node at a time and another move two nodes at a time. In an acyclic list, the fast pointer reaches null. In a cyclic list, both pointers eventually remain inside the loop, and the fast pointer gains one node on the slow pointer during every iteration. Moving around a finite loop while gaining one position per step guarantees a meeting.

Approach

1. 1Return false immediately when head is null or head->next is null, because an empty list and a one-node list without a self-loop cannot contain a cycle.
2. 2Start slow at head and fast at head->next, matching the reference traversal while avoiding an unnecessary first comparison of a pointer with itself.
3. 3Continue while slow and fast refer to different nodes, because equality is the successful proof that both pointers are following the same cycle.
4. 4Before moving fast by two nodes, check fast and fast->next for null, because dereferencing either missing pointer would crash and also proves that the list has ended without a cycle.
5. 5Advance slow by one node and fast by two nodes. Inside a cycle, this changes their relative position by one node per iteration, so the fast pointer cannot pass the slow pointer forever without meeting it.
6. 6Return true when the loop condition stops, because the only way to leave the loop is for slow and fast to point to the same node.

Complexityeach pointer makes only a linear number of advances

Annotated solutionC++ · Floyd's tortoise-and-hare traversal

#include <cstddef>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (!head || !head->next) return false;

        ListNode* slow = head;
        ListNode* fast = head->next;

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

        return true;
    }
};

The important placement is the guard immediately before fast->next->next. At the top of each loop, fast may already be null, or fast->next may be null. Checking both before dereferencing keeps the traversal safe and uses the same fact to conclude that no cycle exists. Once the loop stops naturally, slow == fast is not an ordinary crossing; linked-list pointers can only become equal by landing on the same node.

The set-based alternativesimpler repetition tracking, at the cost of linear memory

You can detect the first repeated node directly with a hash set. Before following a node, check whether its address has already been recorded; a repeat means a cycle, while reaching null means the list ends. This is a different arrangement rather than an optimisation: it is often easier to explain, but it spends O(n) extra space instead of O(1).

#include <cstddef>
#include <unordered_set>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

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

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

        return false;
    }
};

Common mistakestwo pointer bugs that can look correct on short lists