前端算法之双指针之快慢指针（Floyd 判圈法）

• 双指针与快慢指针
• 快慢指针（Floyd 判圈法）
  • 简介
  • 推导

在链表中，快指针和慢指针都可以指向头节点，然后根据问题的要求进行移动。

快指针通常会比慢指针移动得更快，例如每次移动两步，而慢指针则每次移动一步。

在数组或字符串中，快指针和慢指针也可以从起始位置开始遍历。

它们可以根据问题的需求以不同的速度移动。

例如，在判断回文性时，快指针可以从末尾开始向前移动，而慢指针则从起始位置开始向后移动。

需要注意的是，具体问题的要求可能会导致快慢指针的起始位置有所不同。

因此，在应用快慢指针算法时，需要根据问题的特点来确定指针的起始位置，并根据算法的要求调整它们的移动规则。

双指针与快慢指针

双指针和快慢指针都是常用的算法技巧，用于处理不同类型的问题。

双指针是指使用两个指针在数据结构中同时遍历或移动。

这两个指针可以相向而行，也可以分别位于不同的位置。

它们可以按照一定的规则进行移动，解决各种问题。

常见的双指针应用包括：

1. 对撞指针：指针从数组或字符串的两端同时向中间移动，通常用于查找满足某种条件的元素对、判断回文性等。
2. 快慢指针：快指针和慢指针以不同的速度遍历数据结构，用于解决链表相关问题，如判断是否有环、查找中间节点等。

快慢指针是双指针的一种特殊情况，在解决链表问题时常用。

快指针每次移动两步，慢指针每次移动一步，通过它们的不同速度，可以实现对链表的特定操作。

例如，

• 判断链表是否有环时，快慢指针可以同时移动，在存在环的情况下，快指针最终会追上慢指针。

• 在寻找链表的中间节点时，当快指针到达末尾时，慢指针正好在中间节点的位置。

总结起来，双指针是一种通用的算法技巧，而快慢指针则是双指针的一种特殊形式，常用于解决链表相关问题。具体使用哪种技巧取决于问题的性质和要求。

快慢指针（Floyd 判圈法）

简介

对于链表找环路的问题，有一个通用的解法——快慢指针（Floyd 判圈法）。

给定两个指针，分别命名为 slow 和 fast，起始位置在链表的开头。

每次 fast 前进两步，slow 前进一步。

如果 fast
可以走到尽头，那么说明没有环路；如果 fast 可以无限走下去，那么说明一定有环路，且一定存在某个时刻 slow 和 fast 相遇。

当 slow 和 fast 第一次相遇时，我们将 fast 重新移动到链表开头，并让 slow 和 fast 每次都前进一步。

当 slow 和 fast 第二次相遇时，相遇的节点即为环路的开始点。

更多详细内容，请微信搜索“前端爱好者“， 戳我 查看 。

推导

注意这个原理中快慢指针起始位置一定要在同一位置,如果慢指针在head,快指针在head->next,二者走的路程就不满足二倍关系

实现代码

head.next 指向下一个值

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let fast = slow = head
    while(fast && fast.next){
        fast = fast.next.next
        slow = slow.next
        if(fast === slow){
            return true
        }  
    }
    return false
};