Linked List Cycle is today’s problem in the Tekraze DSA series, Day 20, and it introduces one of the neatest tricks in interviews: the slow and fast pointer. We stay with linked lists after Day 18, Reverse Linked List and Day 19, Merge Two Sorted Lists. You get the head of a list and answer one question. Does it loop back on itself?
Also Read: Day 19, Merge Two Sorted Lists for the dummy node and tail pointer pattern, and our Big O helper post for a quick refresher on time and space complexity.
What is the Linked List Cycle problem?
Given the head of a singly linked list, return true if some node can be reached again by following next pointers, and false otherwise. The judge describes the loop with pos, the index the tail points back to, but your function never sees it. You can try the original on LeetCode’s Linked List Cycle page.
text
Input: 3 -> 2 -> 0 -> -4, tail points back to index 1 Output: true Input: 1 -> 2, tail points back to index 0 Output: true Input: 1, no loop Output: false
How should you think about it in plain words?
Imagine two runners on a track. If the track is a straight road, the faster runner just reaches the end. If the track is a loop, the faster runner keeps going around and eventually laps the slower one.
Move one pointer one step at a time and another two steps at a time. If they ever meet, there is a cycle. If the fast one falls off the end, there is not. That picture solves Linked List Cycle before you write a line of code.
What does the brute force Linked List Cycle approach look like?
Walk the list and store every node you visit in a hash set. If you land on a node that is already in the set, you found a loop. If you reach null, the list ends cleanly.
python
def has_cycle_brute(head):
seen = set()
while head:
if head in seen:
return True
seen.add(head)
head = head.next
return False
This runs in O(n) time, which is already fine, but it needs O(n) extra memory for the set. Interviewers almost always follow up on Linked List Cycle by asking you to do it with constant space.
How do we get the optimal Linked List Cycle solution?
Use Floyd’s cycle detection, also called the tortoise and hare. Start slow and fast at the head. In each round, move slow one node and fast two nodes. Keep going while fast and fast.next are not null. If the two pointers ever point at the same node, return true. If the loop ends, return false.
Time is O(n). Without a loop the fast pointer reaches the end in about n / 2 rounds. With a loop, it closes the gap by one node per round once both pointers are inside it, so it catches up within one lap. Space is O(1) because we only keep two pointers.
How does the pointer walk look on the Linked List Cycle sample?
Take the first example, 3, 2, 0, -4, where the tail points back to index 1. Both pointers start on the node holding 3.
| Round | Slow | Fast |
|---|---|---|
| Start | 3 | 3 |
| 1 | 2 | 0 |
| 2 | 0 | 2 |
| 3 | -4 | -4 |
After round 3 both pointers sit on the node holding -4, so the answer is true. Notice that fast never fell off the end, which is the whole signal.
Java solution for Linked List Cycle
java
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
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;
}
// pos is the index the tail points back to, or -1 for no cycle
static ListNode build(int[] vals, int pos) {
ListNode dummy = new ListNode(0), tail = dummy, target = null;
for (int i = 0; i < vals.length; i++) {
tail.next = new ListNode(vals[i]);
tail = tail.next;
if (i == pos) target = tail;
}
tail.next = target;
return dummy.next;
}
static void check(int[] vals, int pos, boolean expected) {
boolean got = new Solution().hasCycle(build(vals, pos));
if (got != expected) throw new AssertionError("Got " + got + " want " + expected);
}
public static void main(String[] args) {
check(new int[]{3, 2, 0, -4}, 1, true);
check(new int[]{1, 2}, 0, true);
check(new int[]{1}, -1, false);
check(new int[]{}, -1, false);
check(new int[]{1}, 0, true);
check(new int[]{1, 2, 3, 4, 5}, -1, false);
check(new int[]{1, 2, 3, 4, 5}, 4, true);
System.out.println("All Java tests passed");
}
}
Python solution for Linked List Cycle
python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head: ListNode | None) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
def build(vals, pos):
"""pos is the index the tail points back to, or -1 for no cycle."""
dummy = tail = ListNode()
target = None
for i, v in enumerate(vals):
tail.next = ListNode(v)
tail = tail.next
if i == pos:
target = tail
tail.next = target
return dummy.next
if __name__ == "__main__":
cases = [
([3, 2, 0, -4], 1, True),
([1, 2], 0, True),
([1], -1, False),
([], -1, False),
([1], 0, True),
([1, 2, 3, 4, 5], -1, False),
([1, 2, 3, 4, 5], 4, True),
]
for vals, pos, expected in cases:
assert has_cycle(build(vals, pos)) == expected
print("All Python tests passed")
The ListNode | None hint needs Python 3.10 or newer. On older versions, drop the hint or use Optional[ListNode].
Rust solution for Linked List Cycle
Safe Rust cannot make a cycle out of Box pointers, because each value has exactly one owner and a cycle would need two. So this version keeps the nodes in a Vec and stores the index of the next node. The slow and fast logic is exactly the same.
rust
// Safe Rust cannot build a cycle with Box, so nodes live in a Vec
// and `next` holds the index of the following node.
struct ListNode {
val: i32,
next: Option<usize>,
}
fn has_cycle(nodes: &[ListNode], head: Option<usize>) -> bool {
let (mut slow, mut fast) = (head, head);
while let Some(f) = fast {
let Some(f2) = nodes[f].next else { return false };
fast = nodes[f2].next;
slow = nodes[slow.unwrap()].next;
if fast.is_some() && slow == fast {
return true;
}
}
false
}
// pos is the index the tail points back to, or -1 for no cycle
fn build(vals: &[i32], pos: i32) -> (Vec<ListNode>, Option<usize>) {
let n = vals.len();
let mut nodes: Vec<ListNode> = vals
.iter()
.enumerate()
.map(|(i, &val)| ListNode { val, next: if i + 1 < n { Some(i + 1) } else { None } })
.collect();
if n > 0 && pos >= 0 {
nodes[n - 1].next = Some(pos as usize);
}
let head = if n > 0 { Some(0) } else { None };
(nodes, head)
}
fn check(vals: &[i32], pos: i32, expected: bool) {
let (nodes, head) = build(vals, pos);
assert_eq!(nodes.iter().map(|n| n.val).count(), vals.len());
assert_eq!(has_cycle(&nodes, head), expected);
}
fn main() {
check(&[3, 2, 0, -4], 1, true);
check(&[1, 2], 0, true);
check(&[1], -1, false);
check(&[], -1, false);
check(&[1], 0, true);
check(&[1, 2, 3, 4, 5], -1, false);
check(&[1, 2, 3, 4, 5], 4, true);
println!("All Rust tests passed");
}
All three programs cover the same seven Linked List Cycle cases: the classic 3, 2, 0, -4 example, a two node loop, a single node with and without a self loop, an empty list, a straight five node list, and a five node list whose tail points to itself. Every check passed in Java, Python and Rust.
What are the 6 tips for an easy Linked List Cycle solution?
- Spot the pattern. Whenever a question says loop, cycle, repeat or detect with constant memory, think slow and fast pointers.
- Guard the fast pointer. Always check
fastandfast.nextbefore jumping two steps, and the null cases take care of themselves. - Compare nodes, not values. Two different nodes can hold the same number, so check identity with
==on Java references orisin Python. - Move first, then compare. Both pointers start at the head, so checking before moving would return
trueon every list. - Know the follow up. To find where the cycle starts, reset one pointer to the head after they meet and move both one step at a time. They meet again at the start of the loop.
- Explain the proof in interviews. Mention the hash set version first, then explain why the fast runner must lap the slow one inside a loop. That short proof often matters more than the code.
What are the common Linked List Cycle mistakes?
- Checking only
fast.nextand crashing whenfastitself is null. - Comparing node values instead of node references.
- Returning
trueright away because both pointers start on the same node. - Marking visited nodes by changing their values, which breaks the input.
- Forgetting the empty list and the single node self loop.
Where is the Linked List Cycle pattern used in the real world?
Cycle detection shows up anywhere one thing points to the next. Garbage collectors and memory tools look for reference loops, and build tools and package managers catch circular dependencies. Random number generators are tested for how soon they repeat.
Floyd’s idea also powers Pollard’s rho, a classic algorithm for factoring numbers in cryptography. If you want the wider theory, the cycle detection overview on Wikipedia covers Floyd’s and Brent’s methods.
Which earlier posts should you read before Linked List Cycle?
Start with the DSA series hub if you want the full roadmap. Then pick the chapter you need:
- Hashing: Day 1, Two Sum for hash map basics, Day 3, Contains Duplicate, Day 4, Valid Anagram and Day 5, Group Anagrams. Day 2, Best Time to Buy and Sell Stock, covers tracking a running minimum.
- Two pointers: Day 6, Valid Palindrome, Day 7, Two Sum II, Day 8, 3Sum and Day 9, Container With Most Water.
- Sliding window: Day 10, Longest Substring Without Repeating Characters, Day 11, Longest Repeating Character Replacement and Day 12, Minimum Window Substring.
- Stacks and queues: Day 13, Valid Parentheses, Day 14, Min Stack, Day 15, Evaluate Reverse Polish Notation, Day 16, Daily Temperatures and Day 17, Implement Queue using Stacks.
- Linked lists: Day 18, Reverse Linked List and Day 19, Merge Two Sorted Lists.
Keep our data structures cheat sheet handy for a quick look at how linked lists compare with arrays, stacks and queues.
Conclusion
Linked List Cycle comes down to one idea: two pointers at different speeds cannot avoid each other inside a loop. Write the hash set version first, then switch to slow and fast to get O(1) space. Your next step is to run the Python version on a list you build yourself, with the tail pointing at different indexes, and watch where the pointers meet.
Frequently asked questions
Can you solve Linked List Cycle without extra memory?
Yes. Floyd’s cycle detection uses only two pointers, so it needs O(1) extra space. The hash set method works too but stores every visited node.
How does Floyd’s cycle detection solve Linked List Cycle?
A slow pointer moves one step and a fast pointer moves two steps. If there is a loop, the fast pointer eventually laps the slow one and they meet. If not, the fast pointer reaches the end.
What is the time and space complexity of Linked List Cycle detection?
Floyd’s method runs in O(n) time and O(1) extra space. The hash set method is also O(n) time but needs O(n) space.
Why compare nodes instead of values?
Different nodes can store the same value. Only comparing node references tells you that the two pointers are really on the same node.
How do you find where the cycle begins?
After slow and fast meet, move one pointer back to the head and step both one node at a time. The node where they meet again is the start of the cycle.
