142. Linked List Cycle II
Model: qwen3.5:9b
Topics: Linked List,Two Pointers
FAANG asked: 1
Acceptance rate: 40.0%
Problem Breakdown
We are given the head of a singly linked list and need to identify if there is a cycle within that structure. If one exists, we must return the specific node where the loop begins (the entry point). We also have an implicit constraint from the follow-up: we cannot modify the nodes’ pointers or use extra memory proportional to .
Inputs:
head: The starting node of a linked list (ListNodeobject).
Outputs:
- Returns the
ListNodewhere the cycle starts. - Returns
Noneif no cycle exists.
Edge Cases & Constraints:
- Empty List: If
headisNone, there can be no cycle. ReturnNone. - No Cycle: The fast pointer will eventually hit a null terminator before meeting the slow pointer. We must handle this gracefully to avoid returning an invalid node or crashing on attribute access (
fast.next). - Cycle at Head vs Tail: The logic should work regardless of where the cycle entry is relative to the head.
- Single Node: If a single node points to itself, that node is the start.
Intuition
A brute-force approach would be to traverse the list and store every visited node in a hash set (or array). Every time we visit a new node, we check if it’s already in our storage. If yes, we found the cycle entry. However, this uses space, which violates the follow-up constraint for constant memory usage.
To solve this with space, I recall Floyd’s Tortoise and Hare algorithm (Two Pointers).
Phase 1: Detection. We use two pointers moving at different speeds—a slow pointer (slow) moves one step per iteration, while a fast pointer (fast) moves two steps. If there is no cycle, fast will eventually reach the end of the list (None). If there is a cycle, they are guaranteed to meet inside the loop because the faster runner laps the slower runner within the finite length of the circle.
Phase 2: Locating Entry. This is the mathematical insight required for space.
Let be the distance from head to the start of the cycle, and let be the cycle’s circumference. When they meet inside the loop at a specific point (let’s call it meeting node), suppose the slow pointer has traveled exactly steps (). The fast pointer travels twice that distance: .
The difference in their distances is , where is the number of laps. Since Fast moves 1 extra step per iteration relative to Slow, they meet when fast has lapped exactly enough times such that:
.
If we reset one pointer back to head and keep the other at the meeting point, moving both forward by 1 node each time, they will collide again. The distance from head to entry is , and the distance from the meeting point (inside loop) backwards along the cycle logic effectively aligns such that this collision happens exactly at the start of the cycle ( steps away).
Approach
- Initialize Pointers: Set
slowandfastboth tohead. - Detect Cycle: Move pointers in a loop: increment
slowby 1,fastby 2. If either pointer becomes null (specifically checkingfast.nextbefore moving), break the loop—no cycle exists. - Handle Collision: Once they meet inside the cycle, we know a cycle exists.
- Find Entry Point: Reset one pointer (
ptr) tohead. Keep the other at the meeting point. Move both pointers forward by exactly 1 step per iteration until they are equal again. The node where they converge is the start of the cycle.
Complexity Analysis
- Time Complexity: . We traverse the list twice in the worst case (once to detect, once to find entry). In a non-cyclic list, we stop early when
fasthits null. - Space Complexity: . We only use two pointers (
slow,fast) and one auxiliary pointer for resetting. No hash sets or recursion stacks are used.
Solution
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def detectCycle(head):
# Handle empty list case immediately
if not head:
return None
slow = fast = head
# Phase 1: Detect cycle using Floyd's algorithm
while True:
# Check for termination (no cycle) before moving pointers.
# We must check both next to avoid AttributeError on null.next
if not fast or not fast.next:
return None
slow = slow.next
fast = fast.next.next
# If they meet, a cycle exists
if slow == fast:
break
# Phase 2: Find the start of the cycle
# Reset one pointer to head.
# The distance from Head -> CycleStart equals Distance(MeetingNode) -> CycleStart (modulo L).
ptr = head
while ptr != slow:
ptr = ptr.next
slow = slow.next
return ptr
# Example usage logic would be handled by the caller passing a ListNode object.
Edge Cases Handled
- Empty List (
headisNone): The function returnsNoneimmediately at the start, preventing traversal errors. - No Cycle: If
fastreaches the end of the list (eitherfastorfast.nextbecomes null), we returnNone. This prevents infinite loops in non-cyclic lists. - Cycle Starts at Head (
pos = 0): The math holds; if , both pointers meet immediately after entering, and resetting one to head results in immediate equality or convergence logic works correctly as distance is zero. - Single Node with Self Loop:
slowmoves to node A,fastmoves to node A (2 steps wraps around). They collide at the single node. Resetting both starts them equal immediately? No, slow stays at collision, ptr resets to head (same node), loop conditionptr != slowis false initially if they are same object reference after reset logic check? Wait:- If cycle length 1 and : Fast moves A->A. Slow moves A->A. They meet immediately in Phase 1.
- Reset ptr to head (Node A). slow at Node A.
ptr != slowis False. Returns Node A. Correct.
- Cycle Starts Near Tail: The distance logic holds regardless of where the entry point lies relative to the tail connection index.