Linked List Cycle

1. Problem Description

Given a linked list, determine whether it contains a cycle.

If some node in the linked list can be reached again by continuously following the next pointer, then the list contains a cycle. An integer pos is used to indicate the position where the tail connects back into the list (0-indexed). If pos is -1, there is no cycle. Note that pos is only used to describe the input and is not passed to the function.

Return true if the linked list contains a cycle; otherwise return false.

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 hasCycle2(head *ListNode) bool {
	count := make(map[*ListNode]bool, 0)
	current := head
	for current != nil {
		if count[current] {
			return true
		}
		count[current] = true
		current = current.Next
	}

	return false
}

3.2. Fast and Slow Pointers

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

        fast = fast.Next.Next
        slow = slow.Next
        // This check must come after advancing the pointers; if checked before advancing, an additional != head condition would be needed
        if fast == slow {
            return true
        }
    }

    return false
}

4. References

• 141. Linked List Cycle - LeetCode
• Entry Node of a Cycle in a Linked List