Linked List Cycle

easy linked list two pointers

Problem

Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to.

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;
}

Explanation

We need to decide if a linked list loops back on itself, and do it with no extra memory. The classic answer is Floyd's tortoise-and-hare: run two pointers at different speeds and watch for them to collide.

The slow pointer moves one node per step; the fast pointer moves two. Think of two runners on a track: if the track is a loop, the faster runner will eventually catch up to and lap the slower one. When that happens, slow and fast point at the same node and we return True.

If there is no cycle, the fast pointer just runs off the end. The loop guard while fast and fast.next catches this — once fast or fast.next is None, we fall out and return False.

Why are they guaranteed to meet inside a loop? Each step the fast pointer gains exactly one position on the slow pointer, so the gap between them shrinks by 1 every iteration until it hits 0. It can never "jump over" without landing on the same node.

Example: [3, 7, 4, 9, 5, 8] where the tail links back to index 2. The fast pointer laps the slow one inside the loop, they coincide, and the answer is true.

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