Linked List Cycle II – Simple Reasoning to Detect a Cycle and Find Its Entry

Problem: Linked List Cycle II (detect a cycle in a singly‑linked list and return the node where the cycle begins).

Approach

The problem actually asks two questions:

Whether a cycle exists.

Return the entry node of the cycle (the node where the cycle starts, e.g., node 2 in the illustration).

How to Determine if a Linked List Contains a Cycle

The classic solution uses two pointers, slow and fast, both starting at the head. In each iteration slow moves one step while fast moves two steps. If at any point slow == fast, a cycle exists; otherwise, reaching the end of the list means no cycle.

1. Define slow and fast pointers, both pointing to the head;
2. Move slow one step and fast two steps each iteration;
3. If after some moves slow == fast, a cycle exists; otherwise it does not.

Pseudo‑code:

// Determine if there is a cycle
fast, slow := head, head
for fast != nil && fast.Next != nil {
    fast = fast.Next.Next
    slow = slow.Next
    if fast == slow { // cycle detected
        break
    }
}

How to Find the Cycle Entry Node

Because fast moves twice as fast as slow, the distance covered by fast is always twice that of slow. After detecting a meeting point inside the cycle, reset slow to the head while keeping fast at the meeting node. Then advance both pointers one step at a time; the node where they meet again is the entry of the cycle.

Complete Code (Go)

/** 
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    // 1. Empty list
    if head == nil {
        return head
    }

    // 2. Determine if there is a cycle
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            break
        }
    }
    // 3. No cycle found
    if fast == nil || fast.Next == nil {
        return nil
    }

    // 4. Cycle exists, find entry node
    slow = head // reset slow to head, fast stays
    for slow != fast {
        fast = fast.Next
        slow = slow.Next
    }

    return slow
}