Linked List Cycle II

14 May 2026 0 Likes

Problem Description

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null. A cycle exists in a linked list if some node can be reached again by continuously following the next pointer. Do not modify the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: Node with value 2
Explanation: The tail node connects back to the node at index 1. The cycle begins at the node having value: 2
Example 2:
Input: head = [1,2], pos = 0
Output: Node with value 1
Explanation: The tail node connects back to the first node itself, so the cycle starts at node: 1
Example 3:
Input: head = [1], pos = -1
Output: null
Explanation: The linked list does not contain any cycle.

Constraints

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

Understanding the Problem

The problem asks us not only to detect whether a cycle exists in a linked list, but also to identify the exact node where the cycle begins.

For example, consider: 1 → 2 → 3 → 4 → 5. If node 5 points back to node 3, the traversal becomes: 1 → 2 → 3 → 4 → 5 → 3 → 4 → 5 .... In this case, the cycle begins at node 3.

One straightforward approach is to store all visited nodes in a set. While traversing the linked list, the first node that appears again is identified as the starting point of the cycle.

There is also a highly optimized mathematical approach that uses fast and slow pointers. Once the two pointers meet inside the cycle, special pointer movement properties allow us to efficiently locate the exact starting node of the cycle without using extra memory.

Hints

The first hint is to detect whether a cycle exists using the fast and slow pointer technique.

Once both pointers meet inside the cycle, reset one pointer to the head of the linked list while keeping the other pointer at the meeting point. Then, move both pointers one step at a time.

The node where they meet again is the starting node of the cycle. This works because of the mathematical relationship between the distances traveled by the two pointers within the linked list cycle.

Solutions

BETTER

HashSet Based Cycle Starting Node Detection Solution

This approach uses a HashSet to track all previously visited nodes while traversing the linked list. The main idea is that if a node appears again during traversal, that node must be the starting point of the cycle.

As we move through the linked list, each node reference is inserted into the set.

If insertion fails because the node already exists in the set, it means the traversal has returned to a previously visited node. That repeated node is identified as the beginning of the cycle.

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

When node 3 appears again, the HashSet already contains that node reference, so we immediately return node 3. If the traversal reaches null without revisiting any node, then no cycle exists and the answer becomes null.

This solution is simple to understand and implement, but it requires additional memory to store visited nodes. 
public class A_Map {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();

        while (head != null) {

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

            head = head.next;
        }

        return null;
    }

    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 detectCycle(self, head):
        visited = set()

        while head:

            if head in visited:
                return head

            visited.add(head)

            head = head.next

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

Floyd’s Cycle Starting Node Detection Solution

This approach uses Floyd’s Cycle Detection Algorithm to first detect the presence of a cycle and then locate the exact node where the cycle begins.

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 contains a cycle, the two pointers eventually meet somewhere inside the loop. Once the meeting point is found, an important mathematical property of cyclic linked lists is applied.

At that stage, one pointer is reset to the head of the linked list while the other pointer remains at the meeting point. Both pointers then move one step at a time.

The node where they meet again is the starting node of the cycle. For example, consider: 1 → 2 → 3 → 4 → 5.

If node 5 points back to node 3, the pointers eventually meet inside the loop. After resetting one pointer to the head and moving both pointers at the same speed, they meet again at node 3, which is the starting point of the cycle.

This solution is highly efficient because it detects and locates the cycle using constant extra space without modifying the linked list.
public class B_FloydCycle {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

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

            if (slow == fast) {

                while (slow != head) {
                    slow = slow.next;
                    head = head.next;
                }

                return slow;
            }
        }

        return null;
    }

    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 detectCycle(self, head):
        slow = head
        fast = head

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

            if slow == fast:

                while slow != head:
                    slow = slow.next
                    head = head.next

                return slow

        return None
Time Complexity
O(n)
Space Complexity
O(1)

Conclusion

The Linked List Cycle II problem is an advanced linked list problem that extends the classic cycle detection concept into locating the exact cycle entry point. The problem demonstrates the power of Floyd’s Cycle Detection Algorithm and the mathematical properties of pointer movement inside cyclic structures.

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

💬 Comments