LeetCode 141 · Easy · Linked List

Linked List Cycle

Given the head of a linked list, return true if some node can be reached again by following next, and false if the list ends.

O(n)time
O(1)space
1 vs 2hops per round

0–10 integers, −99 to 99 · pos = index the tail points back to, or −1 for no cycle

Linked list slow hops 1, fast (red) hops 2 · the yellow arrow is the tail pointing back

public boolean hasCycle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; // 1 hop fast = fast.next.next; // 2 hops if (slow == fast) { return true; } } return false;}
slow
—
fast
—
rounds
0
gap
—

Why it works

  1. Hash set version: remember every node visited and stop on a repeat. O(n) time but O(n) space.
  2. No cycle: fast runs off the end first, after about n/2 rounds, and the loop condition fast != null && fast.next != null stops it safely.
  3. Cycle: both pointers end up going round it. Each round fast moves 2 and slow moves 1, so the gap between them shrinks by exactly 1. It cannot jump over 0, so they must meet within one lap of the cycle.
  4. Compare nodes, not values: slow == fast compares references, which is what you want. Two different nodes can hold the same value, so comparing val would be wrong.
  5. O(n) time, O(1) space: two pointers, no extra memory.
  6. Follow-up (LeetCode 142): to find where the cycle starts, reset one pointer to head after they meet and move both 1 hop at a time. They meet again exactly at the cycle's entry node.