快慢指针：深入理解链表环的检测、入口寻找与环大小计算

作者：宇宙中心我曹县2024.02.23 18:17浏览量：17

简介：在处理链表问题时，尤其是涉及环的情况，快慢指针方法是一个非常实用的技巧。本文将详细解释快慢指针的原理，并通过实际代码展示如何应用它来检测链表环、寻找环入口以及计算环的大小。

链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在某些情况下，链表可能会出现环，即某个节点指向其前面的某个节点，形成一个闭环。快慢指针技术是解决链表环相关问题的一种有效方法。

快慢指针原理

快慢指针由两个指针组成，一个快指针和一个慢指针。快指针每次移动两个节点，而慢指针每次移动一个节点。如果链表中存在环，那么快指针和慢指针最终会在环内的某个节点相遇。如果链表不存在环，那么快指针会先到达链表的末尾。

检测链表环

使用快慢指针可以很容易地检测链表是否包含环。首先，我们初始化两个指针，快指针和慢指针，都指向链表的头节点。然后，我们让快指针每次移动两个节点，慢指针每次移动一个节点。如果快指针和慢指针相遇，那么链表中存在环；否则，链表不存在环。

下面是一个Python示例代码：

  1. class ListNode:
  2.     def __init__(self, val=0, next=None):
  3.         self.val = val
  4.         self.next = next
  6. def hasCycle(head: ListNode) -> bool:
  7.     if not head or not head.next:
  8.         return False
  9.     slow = head
  10.     fast = head.next
  11.     while slow != fast:
  12.         if not fast or not fast.next:
  13.             return False
  14.         slow = slow.next
  15.         fast = fast.next.next
  16.     return True

寻找环入口

一旦我们确定了链表中存在环，下一步是找到环的入口。为了找到环的入口，我们可以让快指针和慢指针以相同的速度移动，每次移动一个节点，直到它们再次相遇。相遇的节点就是环的入口。

下面是一个Python示例代码：

  1. def findCycle(head: ListNode) -> ListNode:
  2.     slow = head
  3.     fast = head.next
  4.     while slow != fast:
  5.         slow = slow.next
  6.         fast = fast.next.next
  7.     return slow

计算环大小

最后，我们需要计算环的大小。为了做到这一点，我们可以让一个指针（例如慢指针）围绕环移动，同时计数器递增。当这个指针再次到达环的入口时，计数器的值就是环的大小。另一种方法是让两个指针以不同的速度移动，直到它们再次相遇。相遇时的位置就是环的入口，然后我们可以使用两个指针来确定环的大小。

下面是一个Python示例代码：

```python
def sizeOfCycle(head: ListNode) -> int:
slow = findCycle(head) # 寻找环入口的函数已经在上面定义过了
count = 0 # 计数器初始化
while slow != head: # 遍历整个环直到回到入口节点
slow = slow.next # 移动慢指针一次
count += 1 # 计数器递增
return count # 返回环的大小

最热文章