Leetcode - 141. Linked List Cycle

Easy

Dec 22, 2025

#linked-list

141. Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: 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
Explanation: 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
Explanation: 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.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Notes

Intuition

Floyd's cycle detection uses two pointers moving at different speeds. If there's a cycle, the fast pointer will eventually lap the slow pointer and they'll meet. If there's no cycle, the fast pointer will reach the end.

Implementation

Initialize both slow and fast pointers to the head. Iterate while fast and fast.next exist. Move slow by one step and fast by two steps. After each move, check if they're equal—if so, a cycle exists. If the loop terminates (fast reaches null), there's no cycle.

Edge-cases

The iteration condition fast and fast.next naturally handles empty lists and lists with a single node.

Time: O(n) — fast pointer traverses at most 2n nodes before meeting slow
Space: O(1) — only two pointers

Complexity

Solution

from typing import Optional
from lcutils import ListNode

# 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:
        slow = head
        fast = head
        while slow and fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                return True
        return False
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()