判断链表是否有环

关注

发布于: 2020 年 04 月 28 日

判断单链表是否有环，以及环的长度和环开始的地方是常见的面试题，如leetcode上的判断是否有环(https://leetcode.com/problems/linked-list-cycle/)和给出环的起点(https://leetcode.com/problems/linked-list-cycle-ii/)，基本上这种问题的解决思路就是快慢指针，这里我们介绍下Brent's Cycle Detection Algorithm， 思路其实就是快慢指针，但是略有不同。
﻿
快慢指针 ﻿
快慢指针的思路其实就是，快指针每次往前移动两次而慢指针每次移动一次，那么如果这个单链表存在环路的话，迟早快指针会和慢指针相遇，否则就不存在环路。
func hasCycle(head *ListNode) bool {
    if head == nil  || head.Next == nil {
        return false
    }
    slow, fast := head, head.Next
    for slow != fast {
        if fast == nil || fast.Next == nil {
            return false
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    return true
}
﻿
Brent's Cycle Detection AlgorithmBrent算法虽然也是用快慢两个指针来检测环，但是区别是快指针每次移动2^N次之后才去移动慢指针，比如，一开始快指针移动2步，然后去更新慢指针，然后4步、8步直到找到环路或者发现并不存在环路。Brent's算法有两个优势，一个是算法常数上来说会快于传统的快慢指针（两者都是O(N))，另外一个是，当要求给出环路的长度的时候，Brent's的算法在检测到环路的同时，就已经得到环路的长度了，不需要额外的计算，相当于了一个side effect。
func hasCycle(head ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    fast, slow := head, head
    stepstaken, steplimit := 0, 2
    for {
        if fast == nil {
            return false
        }
        fast = fast.Next
        stepstaken++
        if fast == slow {
            break
        }
        if stepstaken == steplimit {
            stepstaken = 0
            step_limit = 2
            slow = fast
        }
    }
    return true
}
当算法结束的时候，steps_taken就是环的长度，这里面的逻辑是这样的，我们需要快速把slow和fast两个指针迭代进入环，只要slow和fast两个指针进入环中，此时只要移动快指针N步，当N大于等于环路的长度的时候，那么自然两个指针会相遇，记录快指针移动了多少步的变量steps_taken就是环路的长度了
﻿
环路的起点如果我们同时需要直到环路从哪个node开始，还需要一个些额外的逻辑来处理。
fast, slow = head, head
for stepstaken > 0 {
    fast = fast.Next
    stepstaken--
}
for fast != slow {
    fast = fast.Next
    slow = slow.Next
}
return slow
上面这段代码可以帮助我们找到作为环起点的node，这里初看可能有点不是很直观，但是内在的逻辑很简单。我们假设整个单链表的长度（节点数）为N， 环的长度为L，环的起点的index为I 那么第一个for循环跑完之后，fast指针位于L的位置， 由于N = L + I，那么快指针再走I步就到了loop的起点，此时慢指针处于0的位置，慢指针走I步也到了loop的起点， 所以在第二个loop里，我们让快慢指针同时往前走，如果他们相遇，就代表他们同步到达了loop的起点。
﻿
Referencehttp://www.siafoo.net/algorithm/11
﻿

发布于: 2020 年 04 月 28 日阅读数: 63

原文链接:【http://xie.infoq.cn/article/6a69082406c186f137f0ffceb】。文章转载请联系作者。

Kenn

关注

忘记密码记住我 2018.03.09 加入

Démon de Laplace

发布

暂无评论

创作场景

判断链表是否有环

快慢指针

Brent's Cycle Detection Algorithm

环路的起点

Reference

Kenn

评论