Coding problem · Easy · Linked List

Linked List Cycle

Easy Algorithms & data structures Seen at Amazon, Microsoft, Bloomberg

Given head, determine whether the linked list has a cycle — some node can be reached again by following next. Return true or false. Use O(1) memory.

In the tests the list is given as {values, pos}, where pos is the index the tail links back to (-1 for no cycle); your function just receives head.

Example 1

Input: values = [3,2,0,-4], pos = 1
Output: true

Example 2

Input: values = [1], pos = -1
Output: false

Hints

Hint 1

Move one pointer by one step and another by two. If there's a cycle they must meet.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(1)

Floyd's tortoise and hare: slow moves one step, fast two. Without a cycle fast reaches null; with one, the gap shrinks by one per step inside the cycle so they meet. A visited-set also works but uses O(n) memory.

Reference solution

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

function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

def has_cycle(head: Optional[ListNode]) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

<?php

function hasCycle(?ListNode $head): bool
{
    $slow = $fast = $head;
    while ($fast !== null && $fast->next !== null) {
        $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;
    }
}

Follow-up questions

Return the node where the cycle starts (reset one pointer to head after they meet).

Reverse Linked List · Easy
Merge Two Sorted Lists · Easy
Remove Nth Node From End of List · Medium