Difficulty: Easy · LeetCode 141

Problem

Determine if the linked list has a cycle in it.

Understanding the problem

A cycle exists if a node's next pointer visits a previously seen node.

Intuition

Floyd's Tortoise and Hare: fast pointer moves 2 steps, slow pointer moves 1 step. If cycle exists, fast will catch slow.

Approach

Set slow = head, fast = head.
While fast and fast.next exist:
Advance slow = slow.next, fast = fast.next.next.
If slow == fast, return True.
Return False if loop finishes.

Naive Solution — Brute Force

Store visited node references in a hash set.

Python

class Solution:
    def hasCycle(self, head):
        visited = set()

        while head:
            if head in visited:
                return True

            visited.add(head)
            head = head.next

        return False

C++

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> visited;

        while (head) {
            if (visited.count(head)) {
                return true;
            }

            visited.insert(head);
            head = head->next;
        }

        return false;
    }
};

Java

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();

        while (head != null) {
            if (visited.contains(head)) {
                return true;
            }

            visited.add(head);
            head = head.next;
        }

        return false;
    }
}

JavaScript

var hasCycle = function(head) {
    const visited = new Set();

    while (head) {
        if (visited.has(head)) {
            return true;
        }

        visited.add(head);
        head = head.next;
    }

    return false;
};

Time: O(n) · Space: O(n)

Optimized Code (Python 3)

Python

class Solution:
    def hasCycle(self, head):
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True

        return False

C++

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) {
                return true;
            }
        }

        return false;
    }
};

Java

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                return true;
            }
        }

        return false;
    }
}

JavaScript

var hasCycle = function(head) {
    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            return true;
        }
    }

    return false;
};

Time: O(n) · Space: O(1)

Takeaway

Pattern — Fast (2x) & Slow (1x) Pointers → Floyd's Cycle Detection