Linked List Cycle LeetCode 141 Deep Dive

LeetCode 141 — Linked List Cycle — gives you the head of a singly linked list and asks you to return true if the list contains a cycle. A cycle exists when some node's next pointer points back to a previously visited node, creating an infinite loop rather than terminating at null. The pos parameter in examples indicates which node the tail connects to, but pos is not passed to your function.

The key insight is that a cycle means you can never reach null by following next pointers. Without a cycle, every traversal terminates when you reach the last node whose next is null. With a cycle, traversal loops forever — which is why naive approaches must track visited nodes or use pointer arithmetic to detect the loop.

Follow-up challenge: can you solve it using O(1) memory? The HashSet approach works but uses O(n) extra space to store visited node references. Floyd's cycle detection algorithm answers the follow-up: two pointers at different speeds will eventually meet inside any cycle, requiring no extra memory beyond the two pointer variables.

The HashSet approach is the most intuitive: traverse the list and add each node object (not its value) to a set. Before adding, check if the node is already in the set. If it is, you've visited this node before — a cycle exists, return true. If you reach null without a duplicate, return false.

This approach is O(n) time — each node is visited at most twice (once when traversed, once when checked). Space is O(n) because in the worst case every node is stored in the set before the cycle is detected or null is reached. The set must store node references, not values — a list can have duplicate values without having a cycle.

The HashSet solution's main advantage is simplicity and immediate correctness. It's the first solution most developers think of and it's easy to verify. In an interview you should mention it first, then offer Floyd's algorithm as the O(1) space optimization when the interviewer asks about the follow-up.

Floyd's cycle detection algorithm — also called the tortoise and hare algorithm — uses two pointers initialized at head. The slow pointer (tortoise) advances one step per iteration. The fast pointer (hare) advances two steps per iteration. If the list has no cycle, fast will reach null and the algorithm returns false. If a cycle exists, fast will eventually lap slow and they will meet at the same node.

The algorithm is elegant because it requires no extra data structures — just two pointer variables. Time complexity is O(n): in the worst case fast must travel the entire list before either reaching null or catching slow inside the cycle. Space complexity is O(1): only the two pointers are needed regardless of list length.

Initializing both pointers at head is correct and conventional. Some implementations initialize fast at head.next to avoid the initial equality check, but starting both at head is cleaner and works with the standard while loop condition. The loop terminates when fast is null, fast.next is null (no cycle), or slow equals fast (cycle detected).

Once both pointers enter the cycle, you can analyze their relative motion. Suppose slow is at position i in the cycle and fast is at position j. Each step, slow advances to i+1 and fast advances to j+2. The gap between them (j - i, modulo cycle length) changes by exactly 1 per step — fast gains one position on slow every iteration.

Because the gap decrements by 1 each step and is always a non-negative integer modulo the cycle length, the gap must eventually reach zero. This means they meet within at most cycle_length steps after both are inside the cycle. Fast never 'jumps over' slow because the gap is always an integer and decreases by exactly 1 — it passes through every intermediate value including zero.

The meeting point is not necessarily the start of the cycle — that requires Floyd's cycle detection part II (LeetCode 142). For LeetCode 141, you only need to confirm they meet at all. The meeting proves a cycle exists regardless of where in the cycle the meeting occurs.

Edge cases for linked list cycle are few but important to cover in an interview. An empty list (head is null) has no cycle — fast immediately fails the null check and the function returns false. A single node with next pointing to null has no cycle — fast advances to null and the loop exits. Both cases are handled automatically by the while condition.

A single node pointing to itself (next == self) is a cycle — fast and slow both start at head, slow advances to head.next which is head, fast advances two steps landing back at head; they meet at head and the function returns true. Two nodes pointing to each other (A -> B -> A) is also a cycle — after one iteration slow is at B, fast is at B (two steps: A->B->A... but A = head, then fast.next.next = B again — they meet).

The critical edge case for implementation is checking fast AND fast.next before advancing. If fast.next is null, then fast.next.next would throw a null pointer exception. The condition while (fast != null && fast.next != null) handles lists of both odd and even length without crashing at the end.

Python — Floyd's algorithm: def hasCycle(head): slow, fast = head, head; while fast and fast.next: slow = slow.next; fast = fast.next.next; if slow == fast: return True; return False. O(n) time O(1) space. Python HashSet: def hasCycle(head): seen = set(); node = head; while node: if node in seen: return True; seen.add(node); node = node.next; return False. O(n) time O(n) space.

Java — Floyd's algorithm: 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; }. Note the == operator compares object references in Java, which is correct here — we want to check if the two pointer variables point to the same ListNode object, not just equal values.

Both Python and Java implementations are O(n) time and O(1) space. The Python identity check (slow == fast) compares object identity by default for custom objects, which is what we want. In Java, == on objects also compares references. The only subtle difference: Python uses 'and' to short-circuit, Java uses &&. Both handle the null/None termination identically.

Linked List Cycle II (LeetCode 142) extends this problem: instead of returning true/false, return the node where the cycle begins. It also uses Floyd's algorithm — after the meeting point is found, reset one pointer to head and advance both one step at a time; they meet at the cycle entry. The mathematical proof involves the distance from head to the cycle start equaling the distance from the meeting point to the cycle start.

Happy Number (LeetCode 202) applies cycle detection to a mathematical sequence: replace a number with the sum of squares of its digits repeatedly. If the sequence reaches 1, the number is happy. If it enters a cycle without reaching 1, it is not happy. Floyd's algorithm works perfectly — apply slow and fast to the digit-sum transformation function rather than node.next pointers.

The cycle detection family spans data structures and algorithms: Linked List Cycle (141), Linked List Cycle II (142), Happy Number (202), Find the Duplicate Number (287 — uses Floyd's on index as pointer), and Palindrome Linked List (234 — uses slow/fast to find the middle). Mastering Floyd's algorithm unlocks solutions across this entire family of problems.