Linked List Cycle II

medium linked list two pointers cycle detection

Problem

Return the node where a singly linked list's cycle starts, or null if the list is acyclic. Use O(1) extra space.

Inputlist = 3 → 2 → 0 → -4, tail loops to index 1

Outputnode with value 2

Slow and fast meet inside the cycle; reset slow to head and walk both one step at a time.

values (comma-separated)

cycle starts at index

def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

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

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) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        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) {
                slow = head;
                while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

Explanation

This problem doesn't just ask whether the list has a cycle — it asks for the exact node where the cycle begins, using no extra memory. The elegant answer is Floyd's tortoise-and-hare algorithm in two phases.

Phase one: move slow one step and fast two steps each loop. If there is a cycle, the fast pointer eventually laps the slow one and they land on the same node somewhere inside the loop. If fast reaches the end (None), there is no cycle and we return null.

Phase two is the clever bit. The moment they meet, we reset slow back to the head and now move both pointers one step at a time. The point where they meet again is exactly the cycle's entrance.

Why does that work? There's a neat math fact: the distance from the head to the cycle start equals the distance from the meeting point to the cycle start (going around). So two pointers moving at equal speed from those two places arrive at the entrance together.

Example: 3 → 2 → 0 → -4 with the tail looping back to index 1 (value 2). The pointers meet inside the loop; after resetting one to head and stepping together, they both land on the node with value 2, the cycle entrance.

Time: O(n) Space: O(1)