Linked List Cycle

Easy Problem 50 of 151 Java and Python

Problem

Given head, the head of a linked list, determine whether the list has a cycle: some node can be reached again by following next pointers.

Return true if there is a cycle, otherwise false.

Example 1

Input: head = [3, 2, 0, -4], the tail links to index 1
Output: true

Example 2

Input: head = [1], no cycle
Output: false

Constraints

0 ≤ number of nodes ≤ 10⁴
Follow-up: use O(1) memory.

Explanation

Remembering every visited node works but costs O(n) memory.

Floyd's idea: run two pointers, one moving one step at a time and one moving two. Without a cycle the fast one falls off the end. With a cycle the fast one laps the slow one, and they must meet.

Approach 1 · Naive

Set of visited nodes

Time O(n)
Space O(n)

Walk the list storing each node (by identity). Seeing a node twice means a cycle.

For each node: if it is in the set, return true; otherwise add it.
Return false at the end of the list.

Java

import java.util.*;

class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<>();
        for (ListNode node = head; node != null; node = node.next) {
            if (!seen.add(node)) {
                return true;
            }
        }
        return false;
    }
}

Python

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        node = head
        while node:
            if node in seen:
                return True
            seen.add(node)
            node = node.next
        return False

Approach 2 · Optimal

Floyd's fast and slow pointers

Time O(n)
Space O(1)

Move slow one step and fast two steps. If they ever point to the same node, there is a cycle.

Set slow = fast = head.
While fast and fast.next exist: slow = slow.next, fast = fast.next.next; if slow == fast, return true.
Return false.

Java

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;
    }
}

Python

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

Complexity compared

Approach	Time	Space
Naive Set of visited nodes	O(n)	O(n)
Optimal Floyd's fast and slow pointers	O(n)	O(1)

Key takeaways

Compare nodes by identity (== in Java, is in Python), never by value.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem