#142 Linked List Cycle II
the problem
In plain words
Return the node where the cycle begins, or null if there is no cycle. Do not modify the list.
in head = [3,2,0,-4], pos = 1
out node with value 2 (index 1)
in head = [1,2], pos = 0
out node with value 1 (index 0)
in head = [1], pos = -1
out null
- 0 ≤ number of nodes ≤ 10⁴
- -10⁵ ≤ Node.val ≤ 10⁵
- Follow-up: O(1) memory
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternFast & slow pointers
If slow walked a + b to the meeting point, fast walked 2(a + b), and the extra a + b is whole laps. So a steps from the meeting point land on the entry — exactly what a pointer from head needs.
solutions
From brute force to optimal
Walk with a HashSet; the first node already in the set is the entry.
- Walk the list.
- Return the first node that
seen.addrejects. - Null at the end → no cycle.
Each node visited once.
Set of visited nodes.
class Solution { public ListNode detectCycle(ListNode head) { Set<ListNode> seen = new HashSet<>(); for (ListNode p = head; p != null; p = p.next) { if (!seen.add(p)) return p; // first node we reach twice = the cycle entry } return null; }}Phase 1 detects the meeting point. Phase 2: one pointer from head, one from the meeting point, both speed 1 — they meet at the entry.
- Run slow/fast until they meet (or fast hits null → return null).
- p = head.
- While p != slow: p = p.next, slow = slow.next.
- Return p.
Both phases are at most a few passes over n nodes.
Three references.
class Solution { public ListNode detectCycle(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; }}Dry run
in the room
How to say it in the interview
talk track
- Draw the ρ shape: tail length a, entry, meeting point b into the loop, loop length c.
- Write the equation: 2(a + b) − (a + b) = k·c → a = k·c − b. Then: "walking a steps from the meeting point brings you to the entry."
- Code phase 1 exactly like LC 141, then add the four-line phase 2.
traps
- Starting phase 2 from the wrong node — p must start at head, the other at the meeting point.
- Comparing values instead of node identity.
what they ask next
Follow-ups
Length of the cycle?
After the meeting, keep one pointer still and walk the other until it comes back, counting steps.
before you submit
Edge cases to test
- No cycle → null.
- The cycle starts at the head (pos = 0).
- One node pointing to itself.
- The tail points to itself (a loop of length 1).
practise next
Similar problems
- #141Linked List CycleEasyin Linked Lists
- #287Find the Duplicate NumberMediumin Linked Lists