当前位置： 面试刷题>> 环形链表(经典算法150题)
### 题目描述
**题目：环形链表**
给定一个链表的头节点 `head`，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 `pos` 是 `-1`，则在该链表中没有环。
**示例 1**:
```
输入: head = [3,2,0,-4], pos = 1
输出: true
解释: 链表中有一个环，其尾部连接到第二个节点。
```
**示例 2**:
```
输入: head = [1,2], pos = 0
输出: true
解释: 链表中有一个环，其尾部连接到第一个节点。
```
**示例 3**:
```
输入: head = [1], pos = -1
输出: false
解释: 链表中没有环。
```
### 解题思路
为了检测链表中是否存在环，我们可以使用快慢指针（也称为Floyd的循环查找算法或龟兔赛跑算法）。在这个算法中，我们设置两个指针，一个快指针（每次移动两步）和一个慢指针（每次移动一步）。如果链表中存在环，那么快慢指针最终会在环内的某个位置相遇。如果链表中不存在环，那么快指针会先到达链表末尾。
### PHP 示例代码
```php
val = $val;
$this->next = $next;
}
}
function hasCycle($head) {
if ($head == null || $head->next == null) {
return false;
}
$slow = $head;
$fast = $head->next;
while ($slow != $fast) {
if ($fast == null || $fast->next == null) {
return false;
}
$slow = $slow->next;
$fast = $fast->next->next;
}
return true;
}
// 示例用法
$head = new ListNode(3);
$head->next = new ListNode(2);
$head->next->next = new ListNode(0);
$head->next->next->next = $head->next; // 创建一个环
if (hasCycle($head)) {
echo "链表中存在环";
} else {
echo "链表中不存在环";
}
?>
```
### Python 示例代码
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def hasCycle(head):
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
# 示例用法
head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(0)
head.next.next.next = head.next # 创建一个环
if hasCycle(head):
print("链表中存在环")
else:
print("链表中不存在环")
```
### JavaScript 示例代码
```javascript
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
function hasCycle(head) {
if (!head || !head.next) {
return false;
}
let slow = head;
let fast = head.next;
while (slow !== fast) {
if (!fast || !fast.next) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
// 示例用法
let head = new ListNode(3);
head.next = new ListNode(2);
head.next.next = new ListNode(0);
head.next.next.next = head.next; // 创建一个环
if (hasCycle(head)) {
console.log("链表中存在环");
} else {
console.log("链表中不存在环");
}
```
这些示例代码分别展示了如何在PHP、Python和JavaScript中检测链表中是否存在环。在面试中，理解这种类型的问题并能用至少一种语言实现是很重要的。