141. Linked List Cycle - Detailed Explanation

Problem Statement

Given the head of a singly linked list, determine if the linked list contains a cycle. A cycle occurs when a node’s next pointer points to a previously visited node, creating a loop in the list. If there is a cycle, return true; otherwise, return false.

Examples

Example 1:

• Input: head = [3, 2, 0, -4] with the tail connected to the node at position 1 (0-indexed)
• Output: true
• Explanation: The linked list contains a cycle because the last node (-4) points back to the second node (2).

Example 2:

• Input: head = [1, 2] with the tail connected to the node at position 0
• Output: true
• Explanation: The linked list contains a cycle as the second node (2) points back to the first node (1).

Example 3:

• Input: head = [1] with no cycle (tail does not connect to any node)
• Output: false
• Explanation: The linked list does not contain a cycle.

Constraints

• The number of nodes in the list is in the range [0, 10⁴].
• The value of each node can be any integer.
• The position (if any) that the tail connects to is given as an index. If there is no cycle, this value is -1.

Hints

1. Hash Set Approach:

   • Traverse the list and keep track of visited nodes. If you encounter a node that has already been visited, a cycle exists.

2. Two-Pointer Technique (Floyd’s Cycle Detection):

   • Use two pointers (slow and fast). The slow pointer moves one step at a time, while the fast pointer moves two steps.
   • If the list has a cycle, the fast pointer will eventually meet the slow pointer; otherwise, the fast pointer will reach the end of the list.

Approach 1: Using a Hash Set

Explanation

• Traverse the List: Iterate through each node in the linked list.
• Track Visited Nodes: Maintain a hash set to store references to the nodes you have seen.
• Cycle Detection:
  • For each node, check if it exists in the hash set.
  • If it does, a cycle is detected, and you return true.
  • If not, add the node to the set and continue.
• End of List: If you reach the end of the list (i.e., a null pointer), return false as there is no cycle.

Complexity

• Time Complexity: O(n), where n is the number of nodes in the list.

• Space Complexity: O(n) due to the storage used by the hash set.

Approach 2: Fast and Slow Pointers (Floyd’s Cycle Detection)

Explanation

• Initialize Two Pointers:
  • Slow pointer: Starts at the head and moves one step at a time.
  • Fast pointer: Starts at the head and moves two steps at a time.
• Traverse the List:
  • In each iteration, advance the slow pointer by one node and the fast pointer by two nodes.
• Cycle Detection:
  • If there is no cycle, the fast pointer will eventually reach the end of the list (null).
  • If a cycle exists, the fast pointer will eventually meet the slow pointer inside the cycle.
• Return Result:
  • Return true if the pointers meet; otherwise, return false when the fast pointer reaches the end.

Complexity

• Time Complexity: O(n), where n is the number of nodes.

• Space Complexity: O(1) since only two pointers are used.

Python Code