Skip to main content

🟩 Linked List Cycle (#141)

🔗 Problem Link​

📋 Problem Statement​

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.

💡 Examples​

Example 1​

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where 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 tail connects to the 0th node.

Example 3​

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

🔑 Key Insights & Approach​

Core Observation: Use Floyd's Cycle Detection (Tortoise and Hare) - slow and fast pointers. If they meet, cycle exists.

Why Floyd's Algorithm?

  • O(n) time, O(1) space
  • No additional data structures needed
  • Mathematically proven to work

Approaches:

  1. HashSet to track visited nodes: O(n) time, O(n) space
  2. Floyd's Cycle Detection: O(n) time, O(1) space - optimal

Pattern: "Fast and Slow Pointers" (Floyd's Cycle Detection) pattern.

🐍 Solution: Python​

Approach 1: Floyd's Cycle Detection (Optimal)​

Time Complexity: O(n) | Space Complexity: O(1)

from typing import Optional

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

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            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

Approach 2: HashSet​

Time Complexity: O(n) | Space Complexity: O(n)

from typing import Optional

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        visited = set()
        current = head

        while current:
            if current in visited:
                return True
            visited.add(current)
            current = current.next

        return False

🔵 Solution: Golang​

Approach: Floyd's Cycle Detection​

Time Complexity: O(n) | Space Complexity: O(1)

type ListNode struct {
    Val  int
    Next *ListNode
}

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }

    slow := head
    fast := head

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

        if slow == fast {
            return true
        }
    }

    return false
}

📚 References​