LeetCode: 141 Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that the tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the second node.

Example:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the first node.

Example:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

问题

给定链表的头节点 head，判断链表中是否有环。

如果链表中存在一个节点，通过不断跟随 next 指针可以再次到达这个节点，则链表中有环。在内部，pos 用于表示尾部的 next 指针连接到的节点的索引。请注意，pos 不作为参数传递。

如果链表中存在环，返回 true。否则，返回 false。

解决方案 1

双指针法（快慢指针）

Approach 1 / 方法 1

This solution uses the two-pointer technique, often called the "fast and slow pointer" method. The idea is to have two pointers (slow and fast). The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle, the fast pointer will eventually meet the slow pointer.

该解决方案使用双指针技术，通常称为“快慢指针”法。其思想是使用两个指针（slow 和 fast）。slow 指针每次移动一步，而 fast 指针每次移动两步。如果有环，fast 指针最终会遇到 slow 指针。

Implementation / 实现

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False

        slow = head
        fast = head.next

        while slow != fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next

        return True

Explanation / 解释

1. Check for Edge Cases / 检查边界情况

   if not head or not head.next:
      return False

   • English: We first check if the list is empty or has only one node. If so, it cannot have a cycle, so we return False.
   • Chinese: 我们首先检查链表是否为空或只有一个节点。如果是，它不可能有环，因此我们返回 False。

2. Initialize slow and fast Pointers / 初始化 slow 和 fast 指针

   slow = head
   fast = head.next

   • English: We initialize the slow pointer to the head and the fast pointer to the second node (head.next).
   • Chinese: 我们将 slow 指针初始化为头节点，将 fast 指针初始化为第二个节点（head.next）。

3. Iterate Until the Pointers Meet / 循环直到指针相遇

   while slow != fast:

   • English: We enter a loop that continues until the slow and fast pointers meet. If they meet, there is a cycle.
   • Chinese: 我们进入一个循环，直到 slow 和 fast 指针相遇。如果它们相遇，则说明存在环。

4. Check if fast Reaches the End of the List / 检查 fast 是否到达链表的末尾

   if not fast or not fast.next:
      return False

   • English: If the fast pointer reaches the end of the list (fast or fast.next is None), then there is no cycle, so we return False.
   • Chinese: 如果 fast 指针到达链表的末尾（fast 或 fast.next 为 None），则没有环，因此我们返回 False。

5. Move slow One Step and fast Two Steps / 将 slow 向前移动一步，fast 向前移动两步

   slow = slow.next
   fast = fast.next.next

   • English: We move the slow pointer one step forward and the fast pointer two steps forward.
   • Chinese: 我们将 slow 指针向前移动一步，将 fast 指针向前移动两步。

6. Return True If Pointers Meet / 如果指针相遇，返回 True

   return True

   • English: If the slow and fast pointers meet, it means there is a cycle in the list, so we return True.
   • Chinese: 如果 slow 和 fast 指针相遇，这意味着链表中有环，因此我们返回 True。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n), where n is the number of nodes in the linked list. In the worst case, we traverse all the nodes.
• Space Complexity / 空间复杂度: O(1), as we are using only a constant amount of extra space for the pointers.

Key Concept / 关键概念

• Two-Pointer Technique / 双指针技术: The fast and slow pointer technique is an efficient way to detect cycles in linked lists, leveraging the fact that the faster pointer will eventually lap the slower pointer if there is a cycle.
• 双指针技术: 快慢指针技术是一种检测链表中环的高效方法，利用了如果存在环，快指针最终会赶上慢指针的事实。

解决方案 2

哈希表法

Approach 2 / 方法 2

This solution uses a hash table (set) to keep track of the nodes we’ve visited. If we encounter a node that we’ve seen before, it means there is a cycle.

该解决方案使用哈希表（集合）来跟踪我们访问过的节点。如果我们遇到一个之前见过的节点，这意味着存在一个环。

Implementation / 实现

python

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False

Explanation / 解释

1. Initialize a Hash Set / 初始化哈希集合

   seen = set()

   • English: We initialize an empty hash set to store the nodes we’ve seen.
   • Chinese: 我们初始化一个空的哈希集合来存储我们已经访问过的节点。

2. Iterate Over the Linked List / 遍历链表

   while head:

   • English: We enter a loop that continues as long as the head is not None.
   • Chinese: 我们进入一个循环，只要 head 不为 None，循环就会继续。

3. Check if the Node is Already in the Set / 检查节点是否已经在集合中

   if head in seen:
      return True

   • English: We check if the current node is already in the seen set. If it is, there is a cycle, so we return True.
   • Chinese: 我们检查当前节点是否已经在 seen 集合中。如果是，则存在环，因此我们返回 True。

4. Add the Node to the Set / 将节点添加到集合中

   seen.add(head)

   • English: If the node is not in the set, we add it to the seen set.
   • Chinese: 如果节点不在集合中，我们将其添加到 seen 集合中。

5. Move to the Next Node / 移动到下一个节点

   head
   
   = head.next

   • English: We move the head pointer to the next node in the list.
   • Chinese: 我们将 head 指针移动到链表中的下一个节点。

6. Return False If No Cycle is Found / 如果未找到环，返回 False

   return False

   • English: If we reach the end of the list without finding a cycle, we return False.
   • Chinese: 如果我们到达链表的末尾而未找到环，我们返回 False。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n), where n is the number of nodes in the linked list. We traverse each node exactly once.
• Space Complexity / 空间复杂度: O(n), where n is the number of nodes in the linked list. We use extra space to store the nodes in a set.

Key Concept / 关键概念

• Hash Table for Cycle Detection / 使用哈希表检测环: This approach uses extra space to keep track of visited nodes, making it easy to detect cycles by checking if a node has been seen before.
• 使用哈希表检测环: 这种方法使用额外的空间来跟踪访问过的节点，通过检查节点是否已被访问来轻松检测环。

Comparison / 比较

1. Efficiency / 效率:

   • Two-Pointer Approach / 双指针方法: More space-efficient with O(1) space complexity, making it the preferred method for detecting cycles in linked lists.
   • Hash Table Approach / 哈希表方法: Easier to understand and implement but uses O(n) extra space.

2. Use Case / 使用场景:

   • Two-Pointer / 双指针: Preferred for most scenarios due to its efficiency.
   • Hash Table / 哈希表: Useful if you are already using a hash table or need to detect cycles in a more complex structure.

Summary / 总结

• English: Both the two-pointer and hash table approaches are valid for detecting cycles in linked lists. The two-pointer method is more space-efficient, while the hash table method is more straightforward but uses extra space.
• Chinese: 双指针和哈希表方法都可以有效地检测链表中的环。双指针方法在空间上更高效，而哈希表方法更直观，但使用了额外的空间。

Tips / 提示

• English: Choose the two-pointer approach for its efficiency, but understand the hash table approach for its simplicity and applicability to other data structures.
• Chinese: 选择双指针方法以提高效率，但了解哈希表方法的简单性及其对其他数据结构的适用性。

Solution Template for Similar Questions / 提示

• English: Use the two-pointer technique for in-place detection of cycles and the hash table approach when extra space is not a concern or for more complex cycle detection problems.
• Chinese: 使用双指针技术进行就地环检测；当空间不是问题或处理更复杂的环检测问题时，使用哈希表方法。

5 More Similar Questions / 推荐5问题

1. LeetCode 142. Linked List Cycle II
2. LeetCode 876. Middle of the Linked List
3. LeetCode 160. Intersection of Two Linked Lists
4. LeetCode 234. Palindrome Linked List
5. LeetCode 143. Reorder List

Recommended Resources / 推荐资源

• English: Practice cycle detection in linked lists with both the two-pointer and hash table methods to gain a deeper understanding.
• Chinese: 通过双指针和哈希表方法练习链表中的环检测，以加深理解。

LeetCode #141: Linked List Cycle | Floyd’s Tortoise and Hare Algorithm by Algo Engine

Linked List Cycle – Floyd’s Tortoise and Hare – Leetcode 141 – Python by NeetCode