已知一个链表,计算并返回环形链表中环的长度,若无环则返回0。代码实现
时间: 2024-10-12 16:07:53 浏览: 37
在解决这个问题时,我们可以使用快慢指针法。这种方法的基本思想是创建两个指针,一个快指针每次移动两步,另一个慢指针每次移动一步。如果链表中存在环,那么这两个指针最终会相遇;如果没有环,则快指针会在列表结束时先到达。
以下是Python的一种实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def detectCycle(head):
if not head or not head.next:
return 0 # 如果链表为空或者只有一个节点,没有环
slow = fast = head
has_cycle = False
while fast and fast.next:
slow = slow.next
fast = fast.next.next # 快指针走两步
if slow == fast: # 如果慢指针追上了快指针,说明有环
has_cycle = True
break
if not has_cycle:
return 0 # 没有环
# 现在找到环了,我们需要找到环起点,然后计算环的长度
fast = fast.next # 将快指针移到环内
cycle_len = 1
while slow != fast: # 当慢指针再次追上快指针时,它们之间的距离就是环的长度
slow = slow.next
fast = fast.next
cycle_len += 1
return cycle_len
```
阅读全文