前端算法之双指针之快慢指针(Floyd 判圈法)

发布时间:2023年12月31日

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

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

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

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

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

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

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

双指针与快慢指针

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

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

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

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

常见的双指针应用包括:

  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
};
文章来源:https://blog.csdn.net/BradenHan/article/details/135258451
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。