Linked List Cycle IV
curriculum-track follow-up — find the cycle entry and length; not a canonical LeetCode problem.
Medium
Time
O(n) Space O(1) 4 min read
fast-slow linked-list
Problem#
(curriculum variant — no canonical LeetCode entry.) Given a possibly-cyclic singly linked list, return a pair (entry, length) where entry is the node where the cycle begins and length is the cycle’s length. Return (nullptr, 0) if there’s no cycle.
Examples#
[1 → 2 → 3 → 4 → 5 → 3 → …]→ entry = node3, length = 3.
Constraints#
- Length in
[0, 10^4].
Hints#
Hint 1
Phase 1 to detect, phase 2 to locate the entry, then walk one full lap to count.
Approach#
Combine Cycle and Cycle II: once you find the entry, walk forward until you return to the entry — that’s the cycle length.
Solution#
struct ListNode { int val; ListNode* next; ListNode(int v): val(v), next(nullptr) {}};
pair<ListNode*, int> detectCycleAndLength(ListNode* head) { ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { ListNode* entry = head; while (entry != slow) { entry = entry->next; slow = slow->next; } int len = 1; for (ListNode* p = entry->next; p != entry; p = p->next) ++len; return {entry, len}; } } return {nullptr, 0};}func detectCycleAndLength(head *ListNode) (*ListNode, int) { slow, fast := head, head for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next if slow == fast { entry := head for entry != slow { entry = entry.Next slow = slow.Next } length := 1 for p := entry.Next; p != entry; p = p.Next { length++ } return entry, length } } return nil, 0}from typing import Optional, Tuple
class Solution: def detectCycleAndLength(self, head: Optional[ListNode]) -> Tuple[Optional[ListNode], int]: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: entry = head while entry != slow: entry = entry.next slow = slow.next length = 1 p = entry.next while p != entry: length += 1 p = p.next return entry, length return None, 0function detectCycleAndLength(head) { let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) { let entry = head; while (entry !== slow) { entry = entry.next; slow = slow.next; } let length = 1; for (let p = entry.next; p !== entry; p = p.next) length++; return [entry, length]; } } return [null, 0];}class Solution { public int[] detectCycleAndLength(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { ListNode entry = head; while (entry != slow) { entry = entry.next; slow = slow.next; } int length = 1; for (ListNode p = entry.next; p != entry; p = p.next) length++; return new int[]{entry.val, length}; } } return new int[]{0, 0}; }}function detectCycleAndLength(head: ListNode | null): [ListNode | null, number] { let slow = head, fast = head; while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; if (slow === fast) { let entry = head; while (entry !== slow) { entry = entry!.next; slow = slow!.next; } let length = 1; for (let p = entry!.next; p !== entry; p = p!.next) length++; return [entry, length]; } } return [null, 0];}Editorial#
Two well-known sub-problems wired together: Cycle II for the entry, then a single forward walk for the length. Each operation is O(n) and uses O(1) memory.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#