We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Linked List Cycle

Number: 141

Difficulty: Easy

Paid? No

Companies: Google, Meta, Goldman Sachs, Amazon, Microsoft, Cisco, Oracle, tcs, Adobe, Bloomberg, Uber, Apple, Nvidia, SAP, ZScaler, Yahoo

Problem Description

Determine if a given linked list has a cycle in it. A cycle occurs when a node’s next pointer points to a previous node in the list. Return true if a cycle exists; otherwise, return false.

Key Insights

  • Use two pointers (slow and fast) to traverse the list.
  • The fast pointer moves two steps at a time and the slow pointer moves one step.
  • If the fast pointer ever meets the slow pointer, a cycle exists.
  • If the fast pointer reaches the end of the list (null), the list has no cycle.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes in the linked list. Space Complexity: O(1) as only two pointers are used.

Solution

We use the Floyd's Cycle Detection algorithm (Tortoise and Hare approach). Two pointers, slow and fast, are initialized at the head of the list. The slow pointer moves one step at a time while the fast pointer moves two steps. If the linked list has a cycle, the fast pointer will eventually meet the slow pointer. If the fast pointer reaches the end (i.e., a null pointer), the linked list does not have a cycle.

Code Solutions

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

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # Initialize two pointers, slow and fast, starting from the head.
        slow = head
        fast = head
        
        # Traverse the list until fast pointer reaches the end.
        while fast and fast.next:
            slow = slow.next              # Move slow pointer one step.
            fast = fast.next.next         # Move fast pointer two steps.
            
            # If both pointers meet, there is a cycle.
            if slow == fast:
                return True
        
        # If loop terminates, there is no cycle.
        return False
← Back to All Questions