Linked List Cycle

14 May 2026 0 Likes

Problem Description

Given the head of a linked list, determine whether the linked list contains a cycle. A linked list has a cycle if some node in the list can be reached again by continuously following the next pointer.

Return true if there is a cycle in the linked list, otherwise return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: The tail node connects back to the node at index 1. This creates the cycle: -4 → 2
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: The tail node connects back to the first node, forming a cycle.
Example 3:
Input: head = [1], pos = -1 
Output: false
Explanation: There is no connection back to any previous node, so the linked list does not contain a cycle.

Constraints

1. The linked list contains at least 0 nodes.
2. The number of nodes may vary depending on platform constraints.
3. The linked list may or may not contain a cycle.
4. Efficient solutions are expected to run in linear time using constant extra space.

Understanding the Problem

The problem asks us to determine whether traversing a linked list eventually leads back to a previously visited node. In a normal linked list, traversal always ends when a node points to null.

However, in a cyclic linked list, traversal never truly ends because a node reconnects to an earlier node. For example, consider: 1 → 2 → 3 → 4. If node 4 points back to node 2, the traversal becomes: 1 → 2 → 3 → 4 → 2 → 3 → 4 ... and continues indefinitely.

One straightforward way to detect a cycle is to keep track of previously visited nodes. If the same node is encountered again, a cycle exists.

A more efficient approach uses two pointers moving at different speeds. If a cycle exists, the faster pointer will eventually catch up to the slower pointer inside the loop.

Hints

The first hint is to think about how movement behaves inside a circular path. A highly efficient technique uses one slow pointer and one fast pointer.

The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If the linked list contains a cycle, the fast pointer will eventually meet the slow pointer.

If the linked list does not contain a cycle, the fast pointer will eventually reach null.

Solutions

BETTER

HashSet Based Cycle Detection Solution

This approach uses a HashSet to store all previously visited nodes while traversing the linked list. As we move through the list, each node reference is inserted into the set.

If a node is encountered again, it means the traversal has returned to a previously visited node, confirming the presence of a cycle.

For example, consider: 1 → 2 → 3 → 4. If node 4 points back to node 2, the traversal becomes: 1 → 2 → 3 → 4 → 2.

When node 2 appears again, the HashSet already contains that node reference, so we immediately return true.

If the traversal reaches null without revisiting any node, then no cycle exists.
public class A_Map {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();

        while (head != null) {

            if (!set.add(head)) {
                return true;
            }

            head = head.next;
        }

        return false;
    }

    private class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


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

        while head:

            if head in visited:
                return True

            visited.add(head)

            head = head.next

        return False
Time Complexity
O(n)
Space Complexity
O(n)
OPTIMAL

Floyd's Fast and Slow Pointer Cycle Detection Solution

This approach uses Floyd's Cycle Detection Algorithm, also known as the Tortoise and Hare technique. The main idea is to move two pointers through the linked list at different speeds.

Two pointers are maintained: slow, which moves one step at a time, and fast, which moves two steps at a time. If the linked list does not contain a cycle, the fast pointer eventually reaches null, meaning the traversal ends normally.

However, if a cycle exists, the fast pointer moves faster within the loop and eventually catches up with the slow pointer. For example, in the cyclic linked list 1 → 2 → 3 → 4 → 2 ..., both pointers continue moving inside the cycle. Since the fast pointer moves twice as quickly, the distance between them gradually decreases until both pointers meet.

Once slow == fast, a cycle is confirmed.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


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
public class B_FloydCycle {
    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;
    }

    private class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
Time Complexity
O(n)
Space Complexity
O(1)

Conclusion

The Linked List Cycle problem is a classic linked list problem that introduces the powerful Floyd’s Cycle Detection Algorithm, also known as the Tortoise and Hare technique. The problem demonstrates how pointer movement at different speeds can efficiently detect loops without extra memory.

Mastering this problem helps build a strong understanding of pointer traversal, cycle detection, and linked list optimization techniques, which are commonly used in coding interviews and advanced data structure problems.

💬 Comments