Linked List Cycle II

1. Problem Description

Given a linked list, return the first node where the cycle begins. If the list has no cycle, return null.

An integer pos is used to indicate the position where the tail connects back into the list (0-indexed). If pos is -1, the list has no cycle. Note that pos only describes the input and is not passed as an argument.

2. Approach

1. Approach 1
   • Use a set to record visited nodes
   • If a node has already appeared in the set, the list contains a cycle
2. Approach 2
   • 
   • 
   • Fast and slow pointers
   • Move the fast pointer two steps and the slow pointer one step
   • Although the two pointers may meet, the meeting node is not necessarily the cycle entry

3. Implementation

3.1. map

func detectCycle(head *ListNode) *ListNode {
	count := make(map[*ListNode]bool, 0)
	current := head
	for current != nil {
		if count[current] {
			return current
		}
		count[current] = true
		current = current.Next
	}

	return nil
}

3.2. Fast and Slow Pointers

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    fast := head
    slow := head
    hasCycle := false
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            hasCycle = true
            break
        }
    }

    if !hasCycle {
        return nil
    }

    fast = head
    for fast != slow {
        fast = fast.Next
        slow = slow.Next
    }
    return fast
}

4. References

• Linked List Cycle II (Fast/Slow Pointer Diagram) - LeetCode
• Linked List Cycle II - LeetCode