#141

Easy

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Linked List Cycle

Determine if a given linked list contains a cycle using pointer manipulation or hashing, focusing on detecting repeated nodes efficiently.

hash table linked list two pointers

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1: Hash Table

We can traverse the linked list and use a hash table $s$ to record each node. When a node appears for the second time, it indicates that there is a cycle, and we directly return `true`. Otherwise, when the linked list traversal ends, we return `false`.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        s = set()
        while head:
            if head in s:
                return True
            s.add(head)
            head = head.next
        return False

Solution 2: Fast and Slow Pointers

We define two pointers, $fast$ and $slow$, both initially pointing to $head$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        s = set()
        while head:
            if head in s:
                return True
            s.add(head)
            head = head.next
        return False

Continue Practicing

#142 linked list cycle ii #160 intersection of two linked lists #143 reorder list