Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Linked List Cycle II

MEDIUMProblemSolveExternal Links

Description

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

A cycle exists in a linked list when some node in the list can be reached again by continuously following the next pointer. The tail node's next pointer connects back to some earlier node in the list, forming a loop.

You must not modify the linked list.

Examples

Example 1

Input: head = [3, 2, 0, -4], pos = 1

Output: Node with value 2 (index 1)

Explanation: The linked list is 3 → 2 → 0 → -4, and the tail node (-4) connects back to the node at index 1 (value 2). So the cycle begins at the node with value 2.

Example 2

Input: head = [1, 2], pos = 0

Output: Node with value 1 (index 0)

Explanation: The linked list is 1 → 2, and the tail node (2) connects back to the node at index 0 (value 1). So the cycle begins at the head node itself.

Example 3

Input: head = [1], pos = -1

Output: null

Explanation: The linked list has only one node and its next pointer is null. There is no cycle, so we return null.

Constraints

  • 0 ≤ number of nodes ≤ 10^4
  • -10^5 ≤ Node.val ≤ 10^5
  • pos is -1 or a valid index in the linked list
  • The linked list must not be modified

Editorial

Brute Force - Hash Set

Intuition

The most natural way to find where a cycle begins is to remember every node we have visited. As we walk through the linked list from the head, we store each node's reference in a set. The very first time we encounter a node that is already in our set, that node must be where the cycle starts — because it is the first node we are visiting for the second time.

Think of it like walking through a maze and dropping breadcrumbs at each intersection. The first time you see breadcrumbs already on the ground, you know you have returned to a previously visited intersection — that is where the loop begins.

If we reach a null pointer without ever revisiting a node, there is no cycle.

Step-by-Step Explanation

Let's trace through with head = [3, 2, 0, -4], pos = 1 (tail connects to node at index 1):

Step 1: Initialize an empty hash set and start at the head node (value 3).

  • visited = {}

Step 2: Visit node 3. Is node 3 in the set? No.

  • Add node 3 to the set. Move to the next node.
  • visited = {node3}

Step 3: Visit node 2. Is node 2 in the set? No.

  • Add node 2 to the set. Move to the next node.
  • visited = {node3, node2}

Step 4: Visit node 0. Is node 0 in the set? No.

  • Add node 0 to the set. Move to the next node.
  • visited = {node3, node2, node0}

Step 5: Visit node -4. Is node -4 in the set? No.

  • Add node -4 to the set. Move to the next node.
  • visited = {node3, node2, node0, node-4}

Step 6: Follow -4's next pointer — it leads back to node 2. Is node 2 in the set? YES!

  • Node 2 is the first node we encounter that was already visited.
  • Return node 2 as the start of the cycle.

Hash Set — Detecting Cycle Start — Walk through the linked list storing each visited node in a hash set. The first node we revisit is where the cycle begins.

Algorithm

  1. Create an empty hash set to store visited node references
  2. Start traversing from the head node
  3. For each node:
    • If the node already exists in the set, return it (cycle start found)
    • Otherwise, add the node to the set
  4. If we reach null, return null (no cycle exists)

Code

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> visited;
        ListNode* curr = head;
        
        while (curr != nullptr) {
            if (visited.count(curr)) {
                return curr;
            }
            visited.insert(curr);
            curr = curr->next;
        }
        
        return nullptr;
    }
};
class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        visited = set()
        curr = head
        
        while curr:
            if curr in visited:
                return curr
            visited.add(curr)
            curr = curr.next
        
        return None
public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode curr = head;
        
        while (curr != null) {
            if (visited.contains(curr)) {
                return curr;
            }
            visited.add(curr);
            curr = curr.next;
        }
        
        return null;
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit each node at most once before either finding the cycle start or reaching null. Each hash set lookup and insertion is O(1) on average. So the total time is O(n), where n is the number of nodes.

Space Complexity: O(n)

In the worst case (no cycle), we store all n nodes in the hash set. Even with a cycle, we store at most n distinct node references before detecting the revisited node.

Why This Approach Is Not Efficient

The hash set approach correctly finds the cycle start in O(n) time, but it requires O(n) extra space to store all visited nodes. For a linked list with up to 10^4 nodes, this is manageable, but it is not memory-optimal.

The follow-up question asks: Can you solve this using O(1) memory?

The fundamental issue is that we are using a lookup table to remember where we have been. If we could somehow detect both the presence and the starting point of a cycle using only a fixed number of pointers — without storing every visited node — we would eliminate the extra space entirely.

Floyd's Tortoise and Hare algorithm provides exactly this: it uses just two pointers to detect a cycle and then mathematically pinpoints where the cycle begins.

Optimal Approach - Floyd's Tortoise and Hare

Intuition

This algorithm works in two phases, and the beauty lies in a simple mathematical proof.

Phase 1 — Detect the cycle: Use two pointers, slow (moves one step at a time) and fast (moves two steps at a time). If a cycle exists, the fast pointer will eventually lap the slow pointer and they will meet at some node inside the cycle. If fast reaches null, there is no cycle.

Imagine two runners on a circular track. The faster runner will always catch up to the slower one — they must meet eventually.

Phase 2 — Find the cycle start: Here is the elegant insight. Let us define:

  • F = the number of nodes from the head to the cycle start
  • C = the length of the cycle
  • When slow and fast meet, slow has traveled F + a steps (where a is some distance inside the cycle), and fast has traveled 2(F + a) steps.

Since fast travels exactly twice as far as slow, and the extra distance is all loops around the cycle: F + a ≡ 0 (mod C), which means F ≡ C - a (mod C).

This tells us: if we place one pointer at the head and another at the meeting point, and move both one step at a time, they will meet exactly at the cycle start. The distance from the head to the cycle start (F) equals the distance from the meeting point forward around the cycle to the cycle start (C - a), modulo full cycle lengths.

So after detecting the meeting point, we just reset one pointer to the head, keep the other at the meeting point, and walk both one step at a time. Where they collide is the answer.

Step-by-Step Explanation

Let's trace through with head = [3, 2, 0, -4], pos = 1:

The list structure: 3(idx 0) → 2(idx 1) → 0(idx 2) → -4(idx 3) → back to 2(idx 1)

Phase 1: Detect Cycle

Step 1: Initialize slow = head (node 3), fast = head (node 3).

Step 2: Move slow one step to node 2. Move fast two steps to node 0.

  • slow = node 2 (index 1), fast = node 0 (index 2)

Step 3: Move slow one step to node 0. Move fast two steps: 0 → -4 → 2, so fast = node 2.

  • slow = node 0 (index 2), fast = node 2 (index 1)
  • slow ≠ fast, so continue.

Step 4: Move slow one step to node -4. Move fast two steps: 2 → 0 → -4, so fast = node -4.

  • slow = node -4 (index 3), fast = node -4 (index 3)
  • slow == fast! Cycle detected. Meeting point is node -4.

Phase 2: Find Cycle Start

Step 5: Reset slow to head (node 3). Keep fast at meeting point (node -4).

Step 6: Move both one step: slow → node 2, fast → node 2 (since -4 → 2).

  • slow = node 2, fast = node 2
  • slow == fast! They meet at node 2.

Step 7: Return node 2 — this is where the cycle begins.

Floyd's Algorithm — Two-Phase Cycle Start Detection — Phase 1: slow (1 step) and fast (2 steps) pointers meet inside the cycle. Phase 2: reset slow to head, walk both at same speed — they collide at the cycle start.

Algorithm

Phase 1 — Detect Cycle:

  1. Initialize slow and fast pointers at the head
  2. Move slow one step and fast two steps at each iteration
  3. If slow == fast, a cycle exists — proceed to Phase 2
  4. If fast or fast.next becomes null, return null (no cycle)

Phase 2 — Find Cycle Start:
5. Reset slow to the head. Keep fast at the meeting point.
6. Move both pointers one step at a time
7. When slow == fast, that node is the cycle start — return it

Code

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        
        // Phase 1: Detect cycle
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) {
                // Phase 2: Find cycle start
                slow = head;
                while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        
        return nullptr;
    }
};
class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        
        # Phase 1: Detect cycle
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                # Phase 2: Find cycle start
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        
        return None
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        // Phase 1: Detect cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                // Phase 2: Find cycle start
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        
        return null;
    }
}

Complexity Analysis

Time Complexity: O(n)

Phase 1 takes at most O(n) steps for the two pointers to meet. The slow pointer travels at most n steps before the fast pointer catches it inside the cycle. Phase 2 takes at most O(n) steps — the slow pointer walks at most F steps (the distance from head to the cycle start), and the fast pointer walks the same number of steps from inside the cycle. Combined: O(n) + O(n) = O(n).

Space Complexity: O(1)

We use only two pointer variables (slow and fast) regardless of the list size. No additional data structures are needed, satisfying the follow-up requirement of constant memory.