(1)环形链表 给你一个链表的头节点 head ,判断链表中是否有环。
时间: 2024-03-13 11:38:34 浏览: 91
判断是否有环
根据引用和引用,如果链表中存在环,那么必然存在一个节点可以通过连续跟踪 next 指针再次到达。因此,我们可以使用快慢指针的方法来判断链表中是否存在环。具体来说,我们可以让慢指针 slow 每次移动一步,快指针 fast 每次移动两步,如果链表中存在环,那么快指针一定会在某个时刻追上慢指针,此时就可以判断链表中存在环。如果快指针到达了链表的末尾(即指向 null),那么就可以判断链表中不存在环。
代码如下(Python实现):
```python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, 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
```
阅读全文