How to Solve Linked List Cycle

This problem requires detecting whether a linked list loops back on itself. The most efficient solution uses two pointers moving at different speeds, which naturally exposes cycles without extra space. Alternatively, a hash set can track visited nodes, trading space for simplicity and avoiding pointer errors in complex lists.

Problem Statement

Given the head of a singly linked list, determine if the list contains a cycle. A cycle exists when following the next pointers leads back to a previously visited node. You are not given the position explicitly; only the linked structure matters. Return true if the list has a cycle and false otherwise.

The linked list may have any number of nodes, including zero. Each node's value can range widely, and the cycle, if present, can connect to any node including the head. This problem focuses on pointer manipulation patterns, emphasizing careful traversal to avoid infinite loops while detecting repeated visits accurately.

Examples

Example 1

Input: head = [3,2,0,-4], pos = 1

Output: true

There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2

Input: head = [1,2], pos = 0

Output: true

There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3

Input: head = [1], pos = -1

Output: false

There is no cycle in the linked list.

Constraints

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

Solution Approach

Floyd's Tortoise and Hare (Two Pointers)

Use two pointers moving at different speeds, one slow and one fast. Start both at the head. Move the slow pointer one step at a time and the fast pointer two steps. If a cycle exists, the fast pointer will eventually meet the slow pointer inside the loop. This approach avoids extra memory and efficiently detects cycles by exploiting the relative speeds of pointers.

Hash Set for Visited Nodes

Maintain a hash set of visited nodes while traversing the list. For each node, check if it is already in the set. If it is, a cycle is detected and you return true. If you reach the end of the list (null), return false. This method is straightforward and safe, but it requires O(n) extra space to store all visited nodes.

Edge Case Handling

Pay special attention to empty lists, single-node lists, and lists where the cycle points back to the head. Confirm that the traversal correctly identifies no cycle for null-terminated lists. Ensuring pointers move safely and do not skip nodes prevents infinite loops and misdetections. This attention to edge cases avoids subtle logical errors in linked-list pointer manipulation.

Complexity Analysis

Floyd's two-pointer approach runs in O(n) time with O(1) space, as each pointer moves linearly and no extra storage is needed. The hash set approach also runs in O(n) time but uses O(n) space to store visited nodes. These complexities directly reflect the trade-offs of pointer manipulation versus memory tracking for cycle detection.

What Interviewers Usually Probe

• Do you notice what happens when the fast pointer laps the slow pointer in a cycle?
• Can you optimize the solution to use constant space without losing correctness?
• Will you consider edge cases such as a single node pointing to itself or an empty list?

Common Pitfalls or Variants

Common pitfalls

• Assuming pos is given and trying to access an index instead of following pointers.
• Forgetting to check null before advancing the fast pointer, causing runtime errors.
• Confusing node values with node identity; cycles depend on reference, not values.

Follow-up variants

• Return the starting node of the cycle instead of a boolean to locate the loop entry.
• Determine the cycle length once a cycle is detected to measure loop size.
• Detect multiple cycles in a linked list if nodes form disconnected loops.

How GhostInterview Helps

• Capture the input linked list structure visually or through test examples to analyze pointer paths.
• Guide step-by-step through two-pointer or hash set solutions, explaining time and space complexity implications clearly.
• Support live screen-share or layered view of nodes and pointers, showing exactly where cycles occur and how detection proceeds.

Topic Pages

• Hash Table
• Linked List
• Two Pointers

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the best approach to detect a cycle in a linked list?

Floyd's Tortoise and Hare algorithm using two pointers is optimal for O(1) space, while a hash set is simpler but requires O(n) space.

Does the node value affect cycle detection?

No, cycle detection depends on node references, not the stored values. Two nodes with the same value are distinct unless they are the same object.

How should empty or single-node lists be handled?

An empty list or a single-node list without a self-loop is considered acyclic and should return false immediately to avoid pointer errors.

Can this approach handle cycles connecting to the head?

Yes, both the two-pointer and hash set methods detect cycles regardless of which node the tail connects to, including the head.

What common mistakes occur in linked-list pointer manipulation for this problem?

Typical mistakes include moving pointers without null checks, confusing node identity with values, and infinite loops from improperly advancing fast pointers.