单链表环长计算：快慢指针法算法思想及Python实现

以下是计算单链表中环的长度的一种常见算法思想： 1. 使用快慢指针法来判断链表是否有环。 - 慢指针每次移动一步，快指针每次移动两步。 - 如果快指针追上了慢指针，说明链表有环；否则，链表无环。 2. 当快慢指针相遇时，将慢指针重新指向链表头，然后快慢指针都每次移动一步。 - 再次相遇时，快慢指针走过的步数就是环的长度。 以下是用 Python 实现的代码示例： ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def find_cycle_length(head): 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 # 计算环的长度 slow = head cycle_length = 0 while True: slow = slow.next fast = fast.next cycle_length += 1 if slow == fast: break return cycle_length ``` 这个算法的时间复杂度为 O(n)，其中 n 是链表的节点数。空间复杂度为 O(1)，只使用了固定的几个指针变量。 ######[AI写代码神器 | 338点数解答 | 2024-09-23 13:41:40]