Reverse + Floyd Cycle Visualization for Coding Interviews
Iterative reversal and tortoise/hare cycle detection.
Concept
Reversing a singly linked list and detecting a cycle with Floyd's tortoise and hare are two of the most asked list manipulation questions, and they show up together because both are pure pointer gymnastics with no auxiliary allocation. Reversal is the canonical exercise in thinking in three pointers at once: previous, current, and next. Floyd's cycle detection is the canonical exercise in thinking about relative speed: two walkers, one moving twice as fast as the other, will always meet inside a cycle in O(N) time and O(1) space. Both routines run in place, never need a HashSet of visited nodes, and form building blocks for harder problems like palindrome check, reordering a list, and finding the cycle entry point. If you can produce both from memory on a whiteboard without introducing a null pointer bug, you have the fundamentals nailed.
How it works
Reversal walks the list once and rewires each next pointer to point backward instead of forward. At each step, save the successor so you do not lose the rest of the list, point current.next at the previous node, shift previous to current, and shift current to the saved successor. When current becomes null, the old tail is the new head and previous is the answer. There is no sentinel, no recursion needed, no extra memory. Cycle detection uses two pointers that both start at the head. The slow pointer advances one step per iteration; the fast pointer advances two. If the list is finite and acyclic the fast pointer reaches null first and you return false. If there is a cycle, fast is running inside the loop while slow is still catching up, and the gap closes by one node per iteration until they collide. The meeting is guaranteed to happen within the length of the cycle, so the algorithm is O(N) time and O(1) space with no hash set. A subtle detail is the null check: you must test both fast and fast.next before advancing fast two steps, otherwise you dereference null when the list has even length and no cycle.
Implementation
public class LinkedListOps {
public static class ListNode {
int val;
ListNode next;
ListNode(int v) { this.val = v; }
ListNode(int v, ListNode n) { this.val = v; this.next = n; }
}
/** Reverse a singly linked list in place. O(N) time, O(1) space. */
public static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // save rest of list
curr.next = prev; // rewire backward
prev = curr; // advance prev
curr = next; // advance curr
}
return prev; // new head is the old tail
}
/** Floyd's tortoise and hare. True if a cycle exists. O(N) time, O(1) space. */
public static boolean hasCycle(ListNode head) {
if (head == null) return false;
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;
}
/** Bonus: find the node where the cycle begins, or null. */
public static ListNode cycleStart(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode p = head;
while (p != slow) { p = p.next; slow = slow.next; }
return p;
}
}
return null;
}
}Complexity
- Time:
O(N) for both reverse and cycle detection - Space:
O(1), purely pointer manipulation
Common pitfalls
- Forgetting to save curr.next before rewiring curr.next = prev orphans the rest of the list
- In hasCycle, dereferencing fast.next.next without first checking fast != null && fast.next != null
- Assuming the meeting point is the cycle start; it is not, you need a second pass to find the entry
- Using a HashSet of visited nodes works but wastes O(N) memory when Floyd solves it in O(1)
- Recursive reversal on a long list blows the stack; prefer the iterative form
Key design decisions & trade-offs
- Cycle detection strategy — Chosen: Floyd's two-pointer over HashSet of visited nodes. Same O(N) time but O(1) space instead of O(N), and no hashing overhead per node
- Reversal style — Chosen: Iterative three-pointer over recursion. Recursion is elegant but hits StackOverflowError on lists longer than a few thousand nodes
- Mutation vs copy — Chosen: Reverse in place. The problem rarely forbids mutation and the in-place version is O(1) space versus O(N) for a copy
Practice problems
Interview follow-ups
- Find the node where the cycle begins (Floyd's phase two)
- Reverse only nodes between positions m and n
- Reverse in groups of k nodes
- Detect palindrome list by reversing the second half
- Reorder list as L0 -> Ln -> L1 -> Ln-1 -> ...
Why it matters
Reverse + Floyd Cycle is a core part of the Linked Lists toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".