NUHMAN.com

Introduction

In LeetCode 141, we detected if a cycle exists. Now in LeetCode 142, we need to find where the cycle begins in a linked list.

This problem uses the same Floyd’s Cycle Detection Algorithm (a.k.a. Tortoise and Hare), but with an extra step to locate the cycle's entry point.

Problem Statement

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return nil.

You must not modify the linked list.

Example

go

Input: head = [3,2,0,-4], cycle starts at node index 1 (value = 2)
Output: Node with value 2
go

Input: head = [1,2], cycle starts at node index 0 (value = 1)
Output: Node with value 1
go

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

Approach

✅ Floyd’s Cycle Detection with Entry Point Detection

1. Detect the Cycle using two pointers (slow and fast).
2. If slow == fast, there is a cycle.
3. Reset one pointer to head.
4. Move both pointers one step at a time.
5. The point where they meet again is the start of the cycle.

💡 Why It Works

Let’s break down why resetting one pointer to the head works:

• Suppose the distance from head to the cycle start is a, the distance from cycle start to meeting point is b, and the remaining cycle length is c.
• When slow and fast meet:
• slow = a + b
• fast = a + b + n(b + c) for some integer n
• Because fast moves twice as fast:
• → 2(a + b) = a + b + n(b + c)
• → a = c + (n - 1)(b + c)
• So if we reset one pointer to head and move both one step at a time, they’ll meet at the start of the cycle.

Go Implementation

go

package main

type ListNode struct {
    Val  int
    Next *ListNode
}

func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head

    // Step 1: Detect if a cycle exists
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next

        if slow == fast {
            // Step 2: Find the entry point
            slow = head
            for slow != fast {
                slow = slow.Next
                fast = fast.Next
            }
            return slow
        }
    }

    return nil
}

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

No extra memory is used, and each pointer only traverses the list a few times.

Edge Cases

• Empty list → returns nil
• Single node that points to itself → returns that node
• List with no cycle → returns nil

Conclusion

LeetCode 142: Linked List Cycle II takes cycle detection a step further by identifying where the cycle begins. It’s a brilliant demonstration of Floyd's algorithm and pointer manipulation in action.

This is one of the most elegant and interview-favorite problems when it comes to linked lists.