Linked List

LeetCode 141

LeetCode #141Difficulty: EasyNeetCode 150

LeetCode 141: Linked List Cycle

LeetCode

Given head, the head of a linked list, determine if the linked list has a cycle in it using Floyd's Tortoise and Hare.

Problem Description

Given `head`, the head of a linked list, determine if the linked list has a cycle in it. Return `true` if there is a cycle in the linked list. Otherwise, return `false`.

Examples:
Input: head = [3,2,0,-4], pos = 1
Output: true
Constraints:
  • The number of nodes in list is [0, 10^4].

Core Mental Model

Runner S moves at 1 step/iteration, Runner F moves at 2 steps/iteration. Inside a cycle, relative speed delta is 1 step/iteration. Fast closes the gap by 1 each step, ensuring collision without visited node hash sets.

Formal Loop Invariant

Invariant: Modular gap (fast - slow) % C strictly decreases by 1 in each step.

Key Architectural Takeaway:

Speed deltas eliminate auxiliary memory requirements in cycle detection.

Asymptotic Complexity Analysis

Time ComplexityO(N) Collision occurs in at most N steps.
Space ComplexityO(1) Two pointer references.

Bottleneck: Avoids O(N) Hash Set memory allocation.

Edge Cases & Screener Traps

  • Empty list
  • Single node acyclic