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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Linked List Cycle

Difficulty: Easy

Problem Description

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. Return true if there is a cycle in the linked list. Otherwise, return false.

Key Insights

  • A cycle occurs when a node's next pointer points to a previous node in the list.
  • The problem can be solved using two pointers, known as the "Floyd’s Tortoise and Hare" algorithm.
  • A hash table can be used to track visited nodes, but it requires additional memory.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (for the two-pointer approach) or O(n) (for the hash table approach)

Solution

To determine if a linked list has a cycle, we can use the two-pointer technique. We maintain two pointers, slow and fast. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle, the fast pointer will eventually meet the slow pointer. If the fast pointer reaches the end of the list, then there is no cycle. This approach uses constant space, making it efficient for this problem.

Code Solutions

def hasCycle(head):
    if not head:
        return False
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False
← Back to All Questions