Detect a Cycle in a Linked List

easy linked list two pointers

Problem

A singly linked list either ends with a null next pointer or its tail loops back to some earlier node. Decide which, using O(1) extra memory.

Floyd's idea: a slow pointer advances one node per step; a fast pointer two. If there is a cycle, the fast pointer is guaranteed to "lap" the slow one — the gap shrinks by 1 every step inside the loop. If there is no cycle, fast simply runs off the end.

Inputvalues = [3, 7, 4, 9, 5, 8], cycleAt = 2

Outputtrue

The tail's next points back to the node at index 2.

values (comma-separated)

cycle index (-1 for none)

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

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