快慢双指针中的相对速度
Table of Contents
前言 #
在算法中，快慢双指针是一种解决问题的技巧。常用于链表相关的问题中。
设置两个指针：快指针和慢指针。快指针每次走两步，慢指针每次走一步。
相对速度 #
相对速度是理解快慢双指针技巧的关键点。快指针每次走两步，慢指针每次走一步，那么两者的相对速度就是一步。因此：
- 能够检测是否有环：当慢指针走到环内时，快指针相对慢指针每次只移动一步，因此一定会相遇而不会错过。
- 能够获得环的长度：环的长度就是两次相遇之间移动的次数。
- 能够获得有环链表的节点个数：将慢指针走过的节点存入哈希表中，遇到重复的节点时移动的次数就是节点的个数。
这解决了我们的一部分疑惑：
- 为什么快指针每次走两步而不是走三步、四步：因为相对速度变为了两步、三步，不能检测环且有些节点会被漏掉。