Domain 1EasyCORE

Linked List Cycle

The problem asks us to determine if there is a cycle in a singly linked list given its head node. A cycle exists if following the `next` pointers from any node eventually leads back to that same node.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Linked List#Two Pointers

141. Linked List Cycle

Model: qwen2.5-coder:14b
Topics: Linked List,Two Pointers
FAANG asked: 1
Acceptance rate: 43.1%


Problem Breakdown

The problem asks us to determine if there is a cycle in a singly linked list given its head node. A cycle exists if following the next pointers from any node eventually leads back to that same node.

Inputs:

  • head: The head node of the linked list.

Outputs:

  • Return true if there is a cycle in the linked list; otherwise, return false.

Implicit Constraints or Tricky Edge Cases:

  • An empty linked list (i.e., head is null) should return false.
  • The list could have only one node without a cycle.
  • The list could be very long, so the solution should be efficient in terms of both time and space.

Intuition

A brute-force approach would involve using a hash set to keep track of visited nodes. As we traverse the linked list, we add each node to the set. If we encounter a node that is already in the set, we have detected a cycle. However, this approach requires O(n) space complexity due to the storage of node references.

A more efficient approach involves using two pointers, often referred to as the “tortoise and the hare” algorithm. The idea is to use two pointers, one moving twice as fast as the other. If there is a cycle, the faster pointer will eventually meet the slower pointer inside the cycle. This approach only requires O(1) space.

Approach

We will use the two-pointer technique:

  1. Initialize two pointers, slow and fast. Both start at the head of the linked list.
  2. Move slow one step at a time (slow = slow.next) and fast two steps at a time (fast = fast.next.next).
  3. If there is no cycle, fast will eventually reach the end of the list (null), and we return false.
  4. If there is a cycle, fast will eventually meet slow inside the cycle, and we return true.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the linked list. In the worst case, both pointers traverse the entire list once.
  • Space Complexity: O(1). We only use a constant amount of extra space for the two pointers.

Solution

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def hasCycle(head: ListNode) -> bool:
    if not head or not head.next:
        return False
    
    slow = head
    fast = head.next
    
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    
    return True

Edge Cases Handled

  • Empty List: If the list is empty (head is null), the function returns false.
  • Single Node List: If the list has only one node and no cycle, the function returns false.
  • Cycle at the Start: The algorithm correctly identifies cycles where the tail connects back to the head.
  • Cycle in the Middle: The algorithm correctly identifies cycles that occur anywhere other than the start of the list.