LeetCode Problem 141

Difficulty: 🟢 Easy
Topics: Hash Table, Linked List, Two Pointers

Solution

LeetCode 141, Linked List Cycle

Problem Understanding

This problem asks us to determine whether a singly linked list contains a cycle. A cycle exists when following the next pointers eventually leads back to a node that has already been visited, instead of reaching None.

The input is the head node of a singly linked list. Each node contains a value and a pointer to the next node. The problem statement mentions a variable called pos, but that value is only used internally by LeetCode to construct the test cases. It is not passed into the function, and we do not need to use it directly in our solution.

The expected output is a boolean value:

• Return True if there is a cycle somewhere in the list.
• Return False if the list terminates normally with a None pointer.

The constraints tell us that the list can contain up to 10^4 nodes. This is large enough that inefficient repeated traversals could become problematic, but small enough that linear-time solutions are completely feasible.

Several edge cases are important:

• The list may be empty, meaning head is None.
• The list may contain only one node.
• A single node may point to itself, creating a cycle of length one.
• The cycle may begin at the head node.
• The cycle may begin somewhere in the middle of the list.
• The list may contain no cycle at all.

A naive implementation that repeatedly revisits nodes without tracking them could enter an infinite loop, so cycle detection is the central challenge of the problem.

Approaches

Brute Force Approach

A straightforward solution is to keep track of every node we visit using a hash set.

As we traverse the linked list, we store each node reference in the set. Before visiting a node, we check whether it already exists in the set:

• If it does, we have returned to a previously visited node, which means a cycle exists.
• If we reach None, the list ends normally and no cycle exists.

This approach is correct because every node in an acyclic list is visited exactly once. In a cyclic list, eventually traversal must revisit a node already seen.

The drawback is the extra memory usage. In the worst case, we may store all nodes in the hash set, requiring O(n) additional space.

Optimal Approach

The optimal solution uses Floyd's Cycle Detection Algorithm, also called the tortoise and hare algorithm.

The key observation is that if a cycle exists, two pointers moving at different speeds must eventually meet inside the cycle.

We use:

• A slow pointer that moves one step at a time
• A fast pointer that moves two steps at a time

If there is no cycle, the fast pointer eventually reaches None.

If there is a cycle, the fast pointer loops around the cycle faster than the slow pointer, so eventually the two pointers point to the same node.

This approach avoids extra memory entirely and achieves constant space complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Uses a hash set to track visited nodes
Optimal	O(n)	O(1)	Uses two pointers moving at different speeds

Algorithm Walkthrough

Floyd's Two Pointer Algorithm

1. Initialize two pointers, slow and fast, both starting at the head node.
2. Move through the list while fast and fast.next are not None. This condition ensures that the fast pointer can safely move two steps forward without causing an error.
3. Move the slow pointer one step:

slow = slow.next

4. Move the fast pointer two steps:

fast = fast.next.next

5. After moving both pointers, check whether they point to the same node.
6. If slow == fast, a cycle exists. Return True.
7. If the loop exits because fast or fast.next becomes None, the list terminates normally and no cycle exists. Return False.

Why it works

If the list has no cycle, the fast pointer eventually reaches the end of the list because it moves faster than the slow pointer. Therefore, the algorithm correctly returns False.

If the list contains a cycle, both pointers eventually enter the cycle. Once inside, the fast pointer gains one node on the slow pointer during each iteration because it moves two steps while the slow pointer moves one. Since the cycle has finite length, the fast pointer must eventually catch up to the slow pointer, causing them to meet. Therefore, the algorithm correctly returns True.

Python Solution

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

from typing import Optional

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True

        return False

The implementation starts by assigning both slow and fast to the head node.

The while loop continues only while the fast pointer can safely move two steps forward. This prevents dereferencing None.

Inside the loop:

• slow advances one node
• fast advances two nodes

After moving the pointers, the code checks whether they point to the same node. If they do, a cycle exists.

If the loop terminates naturally, the fast pointer reached the end of the list, meaning no cycle exists.

The solution closely follows the algorithm described earlier and uses only constant additional memory.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    slow := head
    fast := head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next

        if slow == fast {
            return true
        }
    }

    return false
}

The Go implementation is almost identical to the Python version.

The main difference is that Go uses nil instead of None. Pointer comparisons are also explicit, since linked list nodes are represented using pointers.

Go does not require special handling for integer overflow or memory allocation in this problem because the algorithm only manipulates node references.

Worked Examples

Example 1

Input:

3 -> 2 -> 0 -> -4
     ^         |
     |_________|

The tail connects back to the node with value 2.

Iteration	Slow	Fast
Start	3	3
1	2	0
2	0	2
3	-4	-4

At iteration 3, both pointers point to the same node. The algorithm returns True.

Example 2

Input:

1 -> 2
^    |
|____|

Iteration	Slow	Fast
Start	1	1
1	2	1
2	1	1

The pointers meet again, so the algorithm returns True.

Example 3

Input:

1 -> None

Iteration	Slow	Fast
Start	1	1

The loop condition fails immediately because fast.next is None.

The algorithm returns False.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each pointer traverses at most a linear number of nodes
Space	O(1)	Only two pointers are used

The time complexity is linear because each pointer moves through the list at most a constant number of times relative to the number of nodes. Even in the cyclic case, the pointers meet after at most O(n) movements.

The space complexity is constant because the algorithm stores only two node references regardless of input size.

Test Cases

# Definition for testing
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def hasCycle(self, head):
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True

        return False

solution = Solution()

# Test 1: Empty list
assert solution.hasCycle(None) == False  # no nodes

# Test 2: Single node without cycle
node = ListNode(1)
assert solution.hasCycle(node) == False  # single node ending at None

# Test 3: Single node with self-cycle
node = ListNode(1)
node.next = node
assert solution.hasCycle(node) == True  # node points to itself

# Test 4: Two nodes without cycle
a = ListNode(1)
b = ListNode(2)
a.next = b
assert solution.hasCycle(a) == False  # normal linear list

# Test 5: Two nodes with cycle
a = ListNode(1)
b = ListNode(2)
a.next = b
b.next = a
assert solution.hasCycle(a) == True  # cycle back to head

# Test 6: Example 1 from problem statement
a = ListNode(3)
b = ListNode(2)
c = ListNode(0)
d = ListNode(-4)

a.next = b
b.next = c
c.next = d
d.next = b

assert solution.hasCycle(a) == True  # cycle in middle

# Test 7: Longer acyclic list
nodes = [ListNode(i) for i in range(10)]

for i in range(9):
    nodes[i].next = nodes[i + 1]

assert solution.hasCycle(nodes[0]) == False  # long list without cycle

# Test 8: Longer cyclic list
nodes = [ListNode(i) for i in range(10)]

for i in range(9):
    nodes[i].next = nodes[i + 1]

nodes[9].next = nodes[3]

assert solution.hasCycle(nodes[0]) == True  # cycle deep in list

Test	Why
Empty list	Verifies handling of None input
Single node without cycle	Tests smallest non-cyclic list
Single node with self-cycle	Tests cycle of length one
Two nodes without cycle	Verifies simple linear traversal
Two nodes with cycle	Tests small cyclic structure
Example 1	Confirms correctness on provided sample
Longer acyclic list	Verifies traversal over many nodes
Longer cyclic list	Tests cycle detection deep in the list

Edge Cases

Empty List

An empty list means head is None. This case is easy to mishandle if the algorithm assumes at least one node exists. The implementation handles this safely because the while fast and fast.next condition fails immediately when fast is None.

Single Node With No Cycle

A list containing one node that points to None can expose incorrect pointer movement logic. If the algorithm attempts to move fast.next.next without checking fast.next, it would raise an error. The implementation prevents this by checking both fast and fast.next before advancing.

Single Node With Self-Cycle

A node may point to itself directly. Some implementations incorrectly assume cycles require multiple nodes. In this case, both slow and fast pointers eventually point to the same node after movement, so the algorithm correctly identifies the cycle.

Cycle Starting at the Head

The cycle may begin immediately at the first node. This means the pointers never traverse a non-cyclic prefix. Floyd's algorithm still works because the fast pointer eventually laps the slow pointer within the cycle.

Long Non-Cyclic List

A long list without a cycle ensures the algorithm eventually terminates instead of looping forever. The fast pointer reaches None, proving the list is acyclic.