Linked List Cycle II LeetCode 142 Guide

LeetCode 142 — Linked List Cycle II — gives you the head of a singly linked list and asks you to return the node where the cycle begins. If no cycle exists, return null. This is a harder variant of LeetCode 141, which only asks whether a cycle exists; here you must identify the exact entry node.

The problem explicitly requires O(1) extra space. That rules out the obvious HashSet approach where you record every visited node and return the first duplicate. The intended solution is Floyd's cycle detection algorithm, which uses only two pointers regardless of list length.

Understanding this problem requires thinking in two phases. Phase one determines whether a cycle exists at all. Phase two, only reachable if phase one found a meeting point, finds where the cycle starts. The two phases use different pointer strategies, and the transition between them is the key step most people get wrong.

Initialize two pointers at head: slow moves one step per iteration, fast moves two steps per iteration. On each iteration, check whether fast or fast.next is null — if so, you have reached the end of the list and there is no cycle, so return null. If slow and fast ever point to the same node, a cycle exists and that node is the meeting point.

The reason slow and fast must meet inside a cycle: once both pointers enter the cycle, fast is closing the gap by exactly one node per iteration. The gap between them decreases by one each step, so they are guaranteed to collide rather than skip past each other. This is the non-obvious guarantee that makes Floyd's algorithm correct.

The meeting point is somewhere inside the cycle, but it is generally not the cycle entry node. Do not return this node — it is only an intermediate result. Its value is used in phase two to calculate where the entry is. Most implementations that fail LeetCode 142 return the meeting point directly instead of continuing to phase two.

After the meeting point is found in phase one, reset one pointer back to head. Leave the other pointer at the meeting point. Now advance both pointers one step at a time — same speed, no longer slow and fast. The node where they meet again is the cycle entry node.

This works because of the mathematical relationship between the distance from head to the cycle entry, the distance from the cycle entry to the meeting point, and the cycle length. The algebra (covered in the next section) proves that walking from head and walking from the meeting point at the same speed will converge exactly at the entry node.

The implementation detail that trips people up: you must advance both pointers one step at a time in phase two. Many developers instinctively keep the fast pointer moving at two steps because that is what phase one used. That is wrong. Both pointers move at speed one in phase two — that is what the math requires.

Define three distances: a = number of steps from head to the cycle entry node; b = number of steps from the cycle entry to the meeting point (where slow and fast collided in phase one); c = the total length of the cycle. When slow and fast meet, slow has traveled a + b steps total. Fast, moving at twice the speed, has traveled 2(a + b) steps. Fast has also lapped the cycle at least once, so its distance is also a + b + c (at minimum one full extra loop).

Setting the two expressions equal: 2(a + b) = a + b + c. Simplifying: a + b = c. Therefore a = c - b. The quantity c - b is exactly the number of steps remaining in the cycle from the meeting point back to the entry node. So walking a steps from head reaches the entry at the same time as walking c - b steps forward from the meeting point.

This is why resetting one pointer to head and advancing both at the same speed works: both pointers are walking exactly a steps — one from head, one from the meeting point moving forward through the cycle — and they converge at the entry. The math is elegant and the implementation is just four lines once you understand it.

The naive approach to Linked List Cycle II is to use a HashSet: iterate through the list, add each node to the set, and return the first node you encounter that is already in the set. This works correctly and is easy to code. It runs in O(n) time and O(n) space — one set entry per node in the worst case.

Floyd's algorithm achieves the same O(n) time result with O(1) space. It uses only two pointer variables regardless of whether the list has 10 nodes or 100,000 nodes. In memory-constrained environments — embedded systems, kernel-level code, large-scale streaming data — this difference is not academic. It is the difference between the algorithm fitting in cache or not.

In interviews, the O(1) space follow-up is the real test. Solving LeetCode 141 with a HashSet is acceptable. For LeetCode 142, many interviewers specifically ask how you would find the entry node without extra memory. Knowing Floyd's two-phase algorithm and being able to explain the math behind phase two is what separates candidates who have studied the problem from those who truly understand it.

In Python, the solution is two while loops. The first loop runs while fast and fast.next are not null: slow = slow.next, fast = fast.next.next. If the loop exits naturally, return None. If slow == fast inside the loop, break. Then reset slow = head and run the second loop: while slow != fast: slow = slow.next, fast = fast.next. Return slow (or fast — they are the same node).

In Java the logic is identical with explicit null checks: ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) break; } if (fast == null || fast.next == null) return null; slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow. Clean and testable with any linked list fixture.

Both implementations are under 20 lines. The O(n) time comes from the fact that phase one runs at most O(n) steps before the meeting (the cycle length is bounded by n), and phase two runs exactly a steps where a is also bounded by n. The two while loops together touch each node at most a constant number of times.

Happy Number (LeetCode 202) uses the exact same Floyd's cycle detection pattern. Instead of linked list nodes, you follow a sequence of digit-square-sum transformations. If the sequence enters a cycle that does not include 1, the number is not happy. Replacing the linked list with a numeric sequence shows how broadly Floyd's algorithm applies.

Linked List Cycle (LeetCode 141) is the simpler predecessor — it only asks whether a cycle exists, not where it starts. If you already know LeetCode 141, you have phase one of LeetCode 142. The new skill in LeetCode 142 is phase two: understanding why resetting one pointer to head and walking at equal speed finds the entry, which requires the a = c - b proof.

Reorder List (LeetCode 143) and Reverse Linked List II (LeetCode 92) round out the linked list pointer manipulation family. Together, cycle detection (141/142), sublist reversal (92), and list reordering (143) cover the core pointer techniques that appear in the majority of linked list interview questions. Mastering these three problem families prepares you for essentially any linked list variant.