Floyd 判圈算法

Floyd判圈算法(Floyd Cycle Detection Algorithm) 又称为“龟兔赛跑算法”,是一个可以在有限状态机/链表/迭代函数上判断是否有环并求出环的长度和起点的算法。

基本思想

以后使用链表举例,状态机和迭代函数基本同理。
在连表上放置一个快指针和一个慢指针,快指针每次沿链表前进两格(或更多),慢指针则前进一格;如果链表上存在环,快指针就会先于慢指针进入环并在其中循环,等到慢指针进入环之后,快慢指针终会相遇(即快指针扣圈慢指针)。

求解环长与起点

环长比较简单,两指针相遇之后让一个指针原地不动,另一个沿着环再来一圈并计数即可得到环长,重点讨论如何查找环的起点。

查找起点

方法

设两指针相遇于B点,则两指针相遇之后使一个指针回到链表起点,另一个指针在B点;两指针同时一步一步向前移动,两者再次相遇的点就是环的起点。

原理

设两指针相遇时慢指针所走过的距离为i,走过的圈数为a;
链表头到链表起点的距离为m;
环的长度为n;
相遇位置B点与起点的距离为k;
则有:
i=m+an+k
则快指针有:
2
i=m+bn+k
两式相减可得:
i=(a-b)
n
即i是圈长n的整数倍

如此即可得到当头指针沿链表前进m步之后,另一个指针距离起点i+m,而i又是圈长的整数倍,所以两指针在环的起点处相遇。

例题

给定一个链表,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

如果链表中存在环,则返回 true 。 否则,返回 false 。

进阶:

你能用 O(1)(即,常量)内存解决此问题吗?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/linked-list-cycle
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

图片alt

常规解法

哈希表,太LOW了此处省略

Floyd

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast, slow;
        if(head == null)    return false;

        fast = head.next; slow = head;  //此处不让两指针一起出发是为了后面while的条件更好写
        //但是这种写法会使得求圈起点时需要将slow放回头结点后fast自己先走一格,原因可以从公式中推出
        while(fast != slow){
            try{
                fast = fast.next.next;
            }catch(Exception e){
                return false;
            }
            slow = slow.next;
        }
        return true;
    }
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇