Linked List Cycle

Why it belongs on this sheet

This introduces Floyd's cycle detection, which is one of the most reusable pointer tricks in interviews.

Pattern

Fast and slow pointers

Approach

Move one pointer one step at a time and the other two steps. If there is a cycle, they must eventually meet.

Java solution

public class Solution {
  public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;

      if (slow == fast) {
        return true;
      }
    }

    return false;
  }
}

Complexity

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

Interview note

Using a hash set works too, but Floyd is the stronger answer.