每日一题——判断链表中是否有环

**每日一题——判断链表中是否有环**

在数据结构中，链表是一种常见的线性数据结构。然而，在某些情况下，我们需要检查链表中是否存在环，即一个指针从头部开始遍历链表，但最终又回到起始位置。这类问题经常出现在面试中，因此我们需要了解如何解决它。

**什么是环形链表**

环形链表是一种特殊的链表结构，其中某个节点的next指针指向了链表中的另一个节点，而不是null。这种结构形成了一个环，导致链表无法正常遍历。

**判断链表中是否有环**

要判断链表中是否有环，我们可以使用以下方法：

1. **快慢指针法**：这是最常见的方法之一。在这个方法中，我们创建两个指针，分别称为fast和slow。fast指针每次移动两步，而slow指针每次移动一步。如果链表中存在环，那么fast指针最终会追上slow指针。
2. **哈希法**：在这个方法中，我们将链表中的所有节点存储到一个哈希表中。如果某个节点已经存在于哈希表中，则意味着链表中存在环。

下面是使用快慢指针法和哈希法的示例代码：

### 快慢指针法

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef hasCycle(head):
 """
 :type head: ListNode :rtype: 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# Example usage:
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = head # Create a cycleprint(hasCycle(head)) # Output: True

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef hasCycle(head):
 """
 :type head: ListNode :rtype: bool """
 visited = set()
 while head:
 if id(head) in visited:
 return True visited.add(id(head))
 head = head.next return False# Example usage:
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = head # Create a cycleprint(hasCycle(head)) # Output: True